Re: [boost] combinations and permutations

Subject: Re: [boost] combinations and permutations
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2011-01-05 09:37:12

On Jan 5, 2011, at 4:40 AM, Arash Partow wrote:

> 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:

This looks very similar to the next_combination I'm comparing to in the paper.

-Howard

> 
>   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/
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost