RE: [boost] Interest in Combinatorial Algorithms?

From: Paul A. Bristow (boost_at_[hidden])
Date: 2002-06-18 04:13:05

These look very useful (especially if Kaitlin Nelson gets some more
difficult homework assignments in 7th grade
see Mark Nelson, C/C++ Users Journal March 2002 , vole 20(3) p 40 to 45 on
next_permutation.)

I share other reservations about the names.

I look forward to the full code and plenty of examples of use.

Dr Paul A Bristow, hetp Chromatography
Prizet Farmhouse
Kendal, Cumbria
LA8 8AB      UK
[phone]
Mobile [phone]
mailto:pbristow_at_[hidden]

PS Sorry for belated reply.
  -----Original Message-----
  From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]]On Behalf Of Phil Garofalo
  Sent: Tuesday, May 28, 2002 10:05 PM
  To: boost_at_[hidden]
  Cc: pfg23_at_[hidden]
  Subject: [boost] Interest in Combinatorial Algorithms?

  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
  pfg23_at_[hidden]
  Chicago, IL

----------------------------------------------------------------------------
--
  Chat with friends online, try MSN Messenger: Click Here