[boost] Interest in Combinatorial Algorithms?

From: Phil Garofalo (philgarofalo_at_[hidden])
Date: 2002-05-28 16:04:39

Hello, I'm a newcomer to the Boost community. I enjoy the Boost library and find it useful and highly edifying. This is my first attempt at a submission. I am a veteran software engineer (19 years) and C++ programmer. Perhaps I should leave additional introductory biographical information for a later time. Let me get right to the subject.

I've written a suite of generic combinatorial algorithms along the lines of the STL's next_permutation and prev_permutation. Specifically, they are algorithms to implement r-permutations and r-combinations, which are much more useful for practical combinatorial problems. R-permutations and r-combinations permute a subset from a collection versus permuting the entire collection as is the case with next_ and prev_permutation. For instance, give me all possible combinations of doubles players from the Davis Cup Team.

There are eight functions in all and they follow the format and semantics of the STL. They are next_rpermutation, prev_rpermutation, next_rcombination, prev_rcombination. There are user-supplied compare function versions of each. As you know, order is significant in permutations and is not in combinations. Here is an example of one of the functions:

/////////////////////////////////////////////////////////////////////////////
// next_rpermutation
// © Philip F. Garofalo 2002. All rights reserved.
//
template<class RandomAccessIterator>
bool
next_rpermutation(RandomAccessIterator first, RandomAccessIterator r,
 RandomAccessIterator last)
{
 if (!(first < r && r <= last))
  return false;
  
 RandomAccessIterator i = r - 1;
 while(true)
 {
  // find smallest element greater than s[i] after index i.
  RandomAccessIterator k = smallest_greater(i + 1, last, *i);
  
  if (k == last)   // Didn't find it.
   if (i == first)
   {
    sort(first, last); // O(n lg n)
    return false; // we're done--end of permutations
   }
   else
    --i;
  else
  {
   iter_swap(i, k);
   partial_sort(i + 1, r, last); // O(n lg n), heapsort
   return true;
  } // else
 } // while
} // next_rpermutation

Requirements and performance. Generally, input to the functions should be in lexicographical order, at least up to position r for most of the algorithms. Items within the input set should be unique. Although I haven't done a thorough complexity analysis, my initial estimate is that each function performs (r - first)/2 swaps on average.

If there is interest in these functions, then I will post the entire set as directed. Thank you for your interest and for the Boost library. I look forward to hearing your comments.

Phil Garofalo
[e-mail]
Chicago, IL

Chat with friends online, try MSN Messenger: Click Here