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
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
LA8 8AB UK
+44 1539 561830
Mobile +44 7714 33 02 04
PS Sorry for belated reply.
[mailto:boost-bounces_at_[hidden]]On Behalf Of Phil Garofalo
Sent: Tuesday, May 28, 2002 10:05 PM
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:
// © Philip F. Garofalo 2002. All rights reserved.
next_rpermutation(RandomAccessIterator first, RandomAccessIterator r,
if (!(first < r && r <= last))
RandomAccessIterator i = r - 1;
// 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
partial_sort(i + 1, r, last); // O(n lg n), heapsort
} // 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.
-- Chat with friends online, try MSN Messenger: Click Here
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk