On 9/5/05, Howard Hinnant <hinnant@twcny.rr.com> 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