Re: [boost] [gacap]Is any interesting to "Generating All Combinations and Permutations"？

From: Herve Bronnimann (hervebronnimann_at_[hidden])
Date: 2007-12-07 04:55:35

Ben (and others):  I was also thinking, spurred by Howard's  
combination web page, about the following variants for enumerating  
*equivalence* *classes* of permutations:

* next/prev_cyclic_permutation: all cyclic permutations are  
considered equivalent.  If any element is distinct, say *first,  
simply enumerate all the permutations of [++first,last) keeping  
*first fixed.  Complications occur, however, if *first is repeated,  
or if cyclic permutations must be enumerated in lexicographical order  
and the minimum element is repeated.  So the algorithm may have some  
value after all

* next_prev_partial cyclic_permutation: same thing with permutations  
of r among n elements.  I'm not sure how complicated the algorithm  
is...  but it's certainly no longer a simple extension like the full  
cyclic permutation.  For one thing, fixing every first element of the  
partial permutation to each element in turn will enumerate partial  
permutations twice.  I think requiring the first element of the  
partial permutation to be the minimum of these, thus taking every  
iterator middle in the range [first, last-r) and enumerating the  
partial_permutations of [++middle, last) of size r-1 would enumerate  
them in lexicographic order, if all the elements are distinct.  Not  
sure what happens with equal elements, perhaps just skipping over the  
middle such that *middle == *(middle-1) might do the trick.

* next/prev_reverse_permutation: a permutation and its reversal are  
considered equivalent.  The difficulty here seems not to enumerate  
them (you could skip a permutation if, e.g.,  the first is greater  
than the last element, or if the permutation is greater than its  
reversal if you also wish to take care of equal values).  The  
difficulty seems to enumerate them in lexicographic order with at  
most (last - first) swaps and comparisons (the previously proposed  
algorithm has no upper bound on the number of operations needed to  
obtain the next_reverse_permutation).  I think a tweaked  
implementation of next_permutation must be written, it doesn't seem  
possible to just combine the existing algorithms.  For that reason,  
it would deserve to be a standalone algorithm.  Minor point:  the  
name is not a good one, must come up with a better one.

* next/prev_partial_reverse_permutation: same with permutations of r  
among n elements.

Both variants seem rather natural but a bit more far-fetched than the  
unadorned ones.  I'd like to hear if you think they would deserve  
standardization or only clutter the existing proposal.

Regardless of standardization, they might make a nice addition to the  
proposed combination library (http://photon.poly.edu/~hbr/boost/ 
combinations.html) so any comments/thoughts about implementation is  
also welcome.
--
Herve Bronnimann
hervebronnimann_at_[hidden]