Re: [boost] Interest in Combinatorial Algorithms?

From: Phil Garofalo (pfg23_at_[hidden])
Date: 2002-05-30 11:46:42

Thank you Hervé for your expression of interest. And
sorry about the HTML! (Nothing but "plain text" from
here on out.)

I have no objections to improving the names of these
functions. I agree that next_rpermutation can get
easily mixed up with next_permutation. I originally
got the "r-" nomenclature from my old college Discrete
Math text by Richard Johnsonbaugh. My only reservation
of your suggested next_n_element_subset is that it
doesn't indicate permutation or combination. I realize
that next_n_element_permutation_subset starts to get
unwieldy. How about next_n_element_permutation? Still
wordy? I don't know. I don't have a better idea at
moment.

As far as posting the files for review, I can do it at
any time. I don't know how much interest is required
to do so or if I need an official go ahead from
Jeremy.

Regards,

Phil

--- 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