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://listarchives.boost.org/mailman/listinfo.cgi/boost