Re: [boost] Interest in Combinatorial Algorithms?

From: Herve Bronnimann (hbr_at_[hidden])
Date: 2002-05-29 18:14:12

On Tue, May 28, 2002 at 04:04:39PM -0500, Phil Garofalo wrote:
> ....

I can't quote Phil's email appropriately since it was originally posted
in HTML. See other postings about this. I concur with him who said it's
in bad form to post HTML...

This being said, I would value very much the next_rpermutation, etc.
collection of algorithms. Here's a possible application of it, which I
actually needed: in linear algebra, when enumerating all the minors of a
matrix, you need to enumerate all the subsets of size k of a nxn
matrix. For instance, if you want to do geometry with Grassmanian
coordinates, you need an indexing scheme for those subsets.

It's easy enough to write a set of loops to enumerate all pairs, all
triples, etc. of (say) a set of indices, even possible to write
template code for any subset size (at compile time), but having the
algorithm that actually does that dynamically for every subset size, I
would find it very nice.

I submit that these algorithms should be an extension of the STL
algorithms, which is already present in the boost-sandbox. I think the
appropriate place for them would be in a single file, and I suggest in
<boost-sandbox>/boost/sequence_algo/

Phil: you'd need to ask Jeremy for permission. Jeremy?

One comment about the name: r-permutation. I wasn't aware of the name,
and checked. The r refers to "r elements among n". It could easily be
called k-permutation. The full name is ordered selection without
replacement.  There is also naturally r-combinations, where order
doesn't matter. IMHO, I think it would be all for the better to adopt a
less notation-dependent name. Note that there is already
std::next_permutation (easy typo).

Since the interface of Phil's next_rpermutation is very close to that of
std::nth_element, it seems to me that next_n_element_sequence would be
both descriptive and appropriate (if not short). For combinations,
next_n_element_subset would be my first choice. The names sequence and
subset are supposed to reflect the fact that order matters in the first,
but not in the second.

In any case, I like the STL-like interface picked by Phil, and feel
these are very valuable algorithms to be included as natural STL extensions.
Best,
-- 
Hervé