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:
>> Comments welcome. Real world use welcome.
> 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:
is just as good as:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk