Boost logo

Boost :

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


On Jan 4, 2011, at 5:27 PM, Christopher Jefferson wrote:

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

Cool, and kudos! :-)

I suspect that the ultimate solution to this problem will be writing combine_discontinuous and permute in a non-recursive manner, and then saving state as you are doing. If they are non-recursive that will eliminate the need for storing the stack of states and thus the heap allocation. I tried but failed after running out of time on this endeavor. Warning: it's addictive. ;-)

And to get reversible permutations going you need combine_discontinuous3 (or its equivalent) in a non-recursive manner. Ultimately the logic needed here is the ability to call the functor for all permutations of 3 distinct ranges, treated as if they were one continuous range. Then you could skip the combination step altogether. Again, I ran out of time to work this direction.

Anyway, I'm glad you're working on this. for_each_* can easily be built out of next_* if there is no performance penalty for doing so. But the reverse is not true, at least as far as I've discovered. And if I had my druthers, I'd like to be able to choose either the next_* or for_each_* API without performance concerns, depending only upon my application (whether or not I needed to break out of the loop early).

-Howard


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