Permutations.hpp File Reference

Tools for enumeration of permutations. More...

Go to the source code of this file.

Detailed Description

Tools for enumeration of permutations.

First concepts for permutations are needed.
  • The two natural possibilities are:
    • I A permutation as a sequence of objects.
    • II A permutation as a map.
    For the first option we have the advantage of using the standard concept of a range, for the second option we have the advantage of using customisable types.
  • Concept IndexPermutation, Option I:
    1. A random access range (in the Boost::range sense) of size n >= 0 over n different elements from {0, ..., n-1}.
    2. If p is an object of a model of IndexPermutation, then for 0 <= i < boost::size(p) the value p(i) is accessed as *(p + i), which is slightly inconvenient; but by using ranges we have the advantage that all methods for ranges apply to IndexPermutations.
    3. This is likely the most basic and perhaps also the most useful concept here.
    4. Arbitrary permutations of objects can be reduced to IndexPermutations by using indices.
    5. The elements of S_n are now treated as objects for some model of IndexPermutation for a fixed n.
    6. The three basic operations with index-permutations are construction of the identity, composition and inversion.
    7. For the identity we write
      assert(*(IndexPermutations + i) == i)
    8. For composition of index-permutations f and g of the same size we write
      compose(g, f) 
      assert(*(compose(g, f) + i) == *(g + *(f + i)))
    9. And for inversion of index-permutation p we write
      assert(compose(p, inverse(p)) == IndexPermutation(n))
      assert(compose(inverse(p), p) == IndexPermutation(n))
    10. As in Boost::uBLAS, here expression templates should be used, enabling lazy evaluation as well as creation of temporary (for eager evaluation).
    11. An open issue whether we should use unqualified operation names (as above, using ADL) or qualified operation names.
    12. Now, since ranges could be used for everything, it seems better to use OKlib::Matrices::compose and OKlib::Matrices::inverse.
    13. Now it seems that in-place modification of ranges is difficult, and thus perhaps we should consider the second option.
  • Concept IndexPermutation, Option II:
    1. Refines concept FullyConstructibleLo; default construction depends on whether IndexPermutation is refined to have a fixed size n (in which we case get the identity with n elements) or not (in which case we get the empty permutation).
    2. The refinement is called IndexPermutationFixed, and supports the additional operation IndexPermutationFixed::size.
    3. The relation < is lexicographical order.
    4. For an object p of type IP we have the operations
      • size_type<IP>::type
      • size(p) of type size_type
      • p(i) for 0 <= i < size(p) (so IndexPermutation should be a refinement of a function-concept)
      • IP(r) for a range r (interpreted as a cycle; if too long for fixed size, then cut off)
      • range(p) (yields a range of size size(p))
      • p.invert() (in-place modification)
      • p.left_multiply(q), p.right_multiply(q) (in-place modifications)
      • p.resize(m) (in-place modification; extending with the identity or truncating if necessary (can yield undefined behaviour))
    5. A refined concept IndexPermutationExp includes also the expressions
      1. inverse(p)
      2. g * f.
    6. Again expression templates should be used (see above), and now using ADL seems the right choice.
    7. This seems better to me.
    8. Default implementations of IndexPermutation:
      1. as a vector resp.~array
      2. as two vectors (including the inverse) resp.~two arrays.
    9. Special constructions:
      1. transpositions.
Now we know what a permutation is, we need a standard way of enumerating permutations.
  • The best possibility seems just to use ranges of iterators, where the value type is a model of IndexPermutation or IndexPermutationFixed.
  • The concept of a PermutationGenerator then is given by the expressions PermutationGenerator(n) creates a range of iterators of permutation_type, running through all elements of S_n in some order.
  • Refinements are LexicographicalPermutationGenerator and GrayPermutationGenerator.

    One should study the permutation generator from the C++ standard library (it is unclear whether this thing handles equivalent objects or not; I assume it does). Likely this generator must be relatively inefficient, since it must always compute the supporting structure from scratch; thus it's a kind of "non-intrusive" generator, while a more efficient generator would be "intrusive".
    Implement lexicographic enumeration
    • Simple implementations of LexicographicalPermutationGenerator based on the permutation generator from the standard library, and yielding fixed and arbitrary permutations, with and without fast inversion.
    Implement enumeration with only one neighbour-swap to get to the next permutation. This is the equivalent to Gray-codes (see GrayCodes.hpp), and similar considerations apply).

Definition in file Permutations.hpp.