Boost logo

Boost :

Subject: Re: [boost] combinations and permutations
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2011-01-04 11:39:19


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

Hervé Brönnimann wrote a high quality implementation of next_combination which stored this information in the sorted-but-permuted sequence (just like std::next_permutation): http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf And such an algorithm could be the operator++() for a range adaptor. But my tests are showing this approach to be very expensive for some cases (see the plots in my paper).

-Howard


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk