Subject: Re: [boost] combinations and permutations
From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2011-01-04 16:37:21
Den 04-01-2011 19:56, Howard Hinnant skrev:
> On Jan 4, 2011, at 12:00 PM, Thorsten Ottosen wrote:
>
>> Den 04-01-2011 04:40, Howard Hinnant skrev:
>>> Warming this up for tr2:
>>>
>>> http://home.roadrunner.com/~hinnant/combinations.html
>>>
>>> Comments welcome. Real world use welcome.
> I'm curious: Which algorithms of his do you use? And for what
> ballpark ranges of r (distance[first, middle)) and N (distance(first,
> last))?
I can see that I have only used next_combination(), and in my case I
needed to call it for all possible sizes of combinations, so I call
next_combination() inside a for loop.
I have no predetermined bound on N, it depends on my models, but can
range from 10 to 30 to even more, although such N usually become
intractable.
So I haven' used all of Herve's interface, although I think they could
be useful at some point. The thing is, once you need one of these
functions, then it's soo nice to find one implemented and tested.
In general, I believe there are much more efficient ways to visit all
combinations (*) than using the swap-based algorithms provided by Herve,
but they give me a fast solution I can use to unit-test other more
complicated approached (at least for small N).
-Thorsten
(*) I have a paper lying around somewhere .... don't have time to find
it ... something along "subset enumeration trees" or something