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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk