Boost logo

Boost :

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]

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk