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