Re: [boost] combinations and permutations

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