Boost logo

Boost :

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


On Jan 4, 2011, at 3:21 AM, Jeffrey Lee Hellrung, Jr. wrote:

> On 1/3/2011 7:40 PM, Howard Hinnant wrote:
>> Warming this up for tr2:
>>
>> http://home.roadrunner.com/~hinnant/combinations.html
>>
>> Comments welcome. Real world use welcome.
>>
>> -Howard
>
> I need to read this through thoroughly (it looks interesting), but along the same vein, an alternative abstraction is to create a range adaptor that allows iteration through permutations and combinations of a given range. This would be more flexible than a for_each algorithm style of iteration, but possibly less efficient.

I'm not positive but I suspect that a range adaptor approach would suffer precisely the same inefficiencies I've demonstrated in the next_permutation/combination algorithms: The increment operator begins to dominate as shown in the two figures. That being said, the two approaches do not have to compete. They can coexist.

> Have you also considered multipermutations and multicombinations (where repetitions are allowed)?

Yes and no. Yes: one would have to store the repetition count for each element somewhere: perhaps a range of pairs, or perhaps a pair of ranges. Then one would need new algorithms, with new interfaces, to deal with this new data structure. I don't mind admitting that these were some of the hardest algorithms I've ever accomplished as far as getting them both correct and fast (I completely gave up on reversible_permutation several times). I don't relish the idea of complicating them with repetition counts.

So no. :-)

However you can get the same effect by inputting a range with your repetitions represented by multiple values for each value you want to repeat. And those repetitions do not have to be in any order:

   aabbccdd

is just as good as:

   abcdabcd

-Howard


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