Re: [boost] for_each combination/permutation - call for interest

From: Matt Calabrese (rivorus_at_[hidden])
Date: 2005-09-05 21:26:39

On 9/5/05, Howard Hinnant <hinnant_at_[hidden]> wrote:
> 
> On and off for the past 7 months (well, mostly off), I've been working
> on a few combination/permutation algorithms.

I am very interested in this and will check out the code you provided in 
more detail once I finish my current undertakings.

As well, a while back I made some algorithms very similar to your 
combinations algorithm, but with some slight variations. I decided that the 
combination size is, in practice, often known at compile-time, since it just 
about always impacts the design of the overall situation. Because of this, I 
chose to make the combination size be an explicit template argument which 
was used to provide more convenient calling of the passed-in function 
object. Instead of having the algorithms call the passed function object 
with two iterators, you have the option of either having them pass the 
arguments as a single reference to a complete array of pointers to the 
elements (which is often useful for metaprogramming), or they pass each 
argument as an explicit separate function argument (which is good since this 
is how functions usually are already written, meaning that you don't have to 
adapt them before using them with the algorithms).

The obvious difference between this approach and yours is that this means in 
code that the size of the combination must be known at compile-time to be 
used, which is all that I ever encountered in practice. In fact, when 
originally writing the algorithms, I purposely put off making versions where 
the combination size wasn't known until runtime until I encountered a 
situation that needed it, which after a year or so, never happened.

While at first having the combination size be a compile-time argument may 
sound like a downside to some, it actually has some very strong plusses, 
which is why I decided to make it as opposed to going towards a strictly 
runtime solution in the first place. Perhaps the main advantage, as I 
already mentioned, is that the combination size directly affects the 
conceptual number of arguments passed to the function object. Since my 
versions of the combination algorithm provide that size at compile-time, 
rather than always passing a pair of iterators to the function object from 
inside the algorithm, it can just pass the elements of the combination as 
separate arguments. This is very beneficial since more often than not, a 
version taking separate arguments already naturally exists and in order to 
make it take an iterator range, you would have to adapt it. That step of 
adaptation is therefore removed.

For instance, one operation which I used was the collision of two objects in 
a physics simulation. I'll demonstrate using a function, though in actuality 
it was a type with overloaded operator ().

void check_collision( object_type left, object_type right );

// 2 being the combination size (colliding two objects at a time)
// though it can be left out to default to 2
for_each_combination< 2 >( my_objects.begin(), my_objects.size(), 
check_collision ); // where my_objects is a container of object_type

This is nice, again, since the collision function, or whatever function you 
would use, is probably already naturally implemented to take the amount of 
parameters needed for the combination. It also generally wouldn't make sense 
to check for collision between anything other than two objects at once, so 
the need for a version which takes an iterator range is simply unnatural. 
Obviously here, and many other places, this is because the combination size 
is directly a part of the code's design known at compile-time, so it makes 
sense to have the argument as a template argument as opposed to being passed 
at runtime.

Again, the downside of this is that combination size must be known at 
compile-time, though in real-world applications, that is typically all that 
I personally have ever encountered. Of course, this is not always the case, 
so both styles of the algorithm would be very nice to have handy.

I was going to include the code with this post, but I switched compilers 
since I last used the algorithms, and after testing it just now, I have a 
dreaded internal compiler error which I'd like to clean up. I'm currently 
working on a number of other projects, so it may be a while before I go back 
and try to figure out what is wrong -- this post was more to point out that 
having a version with compile-time combination size passing is actually very 
beneficial, anyway, and the implementation is very trivial if you have any 
experience with template and preprocessor metaprogramming.

-- 
-Matt Calabrese