Re: [boost] combinations and permutations

Subject: Re: [boost] combinations and permutations
From: Arash Partow (arash_at_[hidden])
Date: 2011-01-05 04:40:50

On 4/01/2011 2:40 PM, Howard Hinnant wrote:
> Warming this up for tr2:
>
> http://home.roadrunner.com/~hinnant/combinations.html
>
> Comments welcome.  Real world use welcome.
>

Have you considered this as the implementation for the combinations routine:

    template <typename Iterator>
    inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
    {
       /* Credits: Thomas Draper */
       if ((first == last) || (first == k) || (last == k))
          return false;
       Iterator itr1 = first;
       Iterator itr2 = last;
       ++itr1;
       if (last == itr1)
          return false;
       itr1 = last;
       --itr1;
       itr1 = k;
       --itr2;
       while (first != itr1)
       {
          if (*--itr1 < *itr2)
          {
             Iterator j = k;
             while (!(*itr1 < *j)) ++j;
             std::iter_swap(itr1,j);
             ++itr1;
             ++j;
             itr2 = k;
             std::rotate(itr1,j,last);
             while (last != j)
             {
                ++j;
                ++itr2;
             }
             std::rotate(k,itr2,last);
             return true;
          }
       }
       std::rotate(first,k,last);
       return false;
    }

Sourced from: http://marknelson.us/2002/03/01/next-permutation/