Re: [boost] combinations and permutations

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