Re: [boost] Interest in Combinatorial Algorithms?

From: Phil Garofalo (pfg23_at_[hidden])
Date: 2002-06-05 11:45:08

Herve, I've posted my combinatorial algorithms in
rcombo.hpp to boost-sandbox in the sequence_algo
subdirectory. I've also checked up a test program
named rcombo.cpp and an example program named
rcomboex.cpp. At the moment the test program doesn't
adhere to Boost's rigorous test framework, but I will
upgrade it as soon as I can. I have not uploaded a
make file, primarily because I'm using Visual Studio
and it seems like Unix make is the common build
utility. The programs should be fairly trivial to
build as they're only single C++ files that include
rcombo.hpp (see rcombo.html in the docs directory). I
will upload a unix-style make for rcombo also.

As far as the function names go, I renamed the
algorithms next_r_permutation, prev_r_combination, and
the like. The inclusion of the underscore after the
"r" should provide sufficient typographical
distinction from next_permutation. I cling to the
phrase "r-permutation" because it is the commonly used
verbiage for ordered selection of r objects from n
objects without replacement. Do a lookup of
"r-permutation" on google.com to confirm. Although I
understand your reasoning for using the word
"sequence" for permutation and "subset" for
combination, I believe those terms are less precise
and have well known meanings in other contexts (e.g.,
STL _sequence_ containers are not necessarily in
lexicographical order). Also the use of permutation
and combination in the function names is harmonious
with STL's next_ and prev_permutation.

Nevertheless, I thank you for your insight and look
forward to hearing your comments and seeing your
revisions (and those of others).

Regards,

Phil Garofalo

--- Herve Bronnimann <hbr_at_[hidden]> wrote:
> 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é
> 
> 

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com