Re: [boost] combinations and permutations

Subject: Re: [boost] combinations and permutations
From: Christopher Jefferson (chris_at_[hidden])
Date: 2011-01-04 17:27:07

On 4 Jan 2011, at 16:39, Howard Hinnant wrote:

> On Jan 4, 2011, at 11:05 AM, Anthony Williams wrote:
> 
>> Howard Hinnant <howard.hinnant_at_[hidden]> writes:
>> 
>>> On Jan 4, 2011, at 6:22 AM, Christopher Jefferson wrote:
>>> 
>>>> 
>>>> On 4 Jan 2011, at 03:40, Howard Hinnant wrote:
>>>> 
>>>>> Warming this up for tr2:
>>>>> 
>>>>> http://home.roadrunner.com/~hinnant/combinations.html
>>>>> 
>>>>> Comments welcome.  Real world use welcome.
>>>> 
>>>> For TR2, it would be nice to produce a range object, so we could write:
>>>> 
>>>> for(perm: reversible_permutation(first, mid, last) )
>>>> f(perm);
>>> 
>>> Not positive, but I believe (if one could figure out how to code it)
>>> would suffer the exponential cost of incrementation demonstrated for
>>> next_partial_permutation and next_combination in "Performance
>>> Considerations" shown in:
>>> 
>>> http://home.roadrunner.com/~hinnant/combinations.html
>> 
>> Couldn't the range adaptor object --- or the iterators generated from it
>> --- store the intermediate information about where in the series of
>> swaps it was? Sort of a continuation in your for_each_permutation()
>> functions.
> 
> I don't know.  Show me the code. :-)

I am currently working on the code. I believe I am getting similar performance. However, I currently have a very heavy-duty iterator (it contains a heap-allocated array, effectively storing the stack of an algorithm like yours). Very important that it doesn't get post-incremented!

Chris