Tools for enumeration of permutations.
More...
Go to the source code of this file.
Detailed Description
Tools for enumeration of permutations.
 Todo:
 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:

A random access range (in the Boost::range sense) of size n >= 0 over n different elements from {0, ..., n1}.

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.

This is likely the most basic and perhaps also the most useful concept here.

Arbitrary permutations of objects can be reduced to IndexPermutations by using indices.

The elements of S_n are now treated as objects for some model of IndexPermutation for a fixed n.

The three basic operations with indexpermutations are construction of the identity, composition and inversion.

For the identity we write
IndexPermutation(n)
assert(*(IndexPermutations + i) == i)

For composition of indexpermutations f and g of the same size we write
compose(g, f)
assert(*(compose(g, f) + i) == *(g + *(f + i)))

And for inversion of indexpermutation p we write
inverse(p)
assert(compose(p, inverse(p)) == IndexPermutation(n))
assert(compose(inverse(p), p) == IndexPermutation(n))

As in Boost::uBLAS, here expression templates should be used, enabling lazy evaluation as well as creation of temporary (for eager evaluation).

An open issue whether we should use unqualified operation names (as above, using ADL) or qualified operation names.

Now, since ranges could be used for everything, it seems better to use OKlib::Matrices::compose and OKlib::Matrices::inverse.

Now it seems that inplace modification of ranges is difficult, and thus perhaps we should consider the second option.

Concept IndexPermutation, Option II:

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

The refinement is called IndexPermutationFixed, and supports the additional operation IndexPermutationFixed::size.

The relation < is lexicographical order.

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

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() (inplace modification)

p.left_multiply(q), p.right_multiply(q) (inplace modifications)

p.resize(m) (inplace modification; extending with the identity or truncating if necessary (can yield undefined behaviour))

A refined concept IndexPermutationExp includes also the expressions

inverse(p)

g * f.

Again expression templates should be used (see above), and now using ADL seems the right choice.

This seems better to me.

Default implementations of IndexPermutation:

as a vector resp.~array

as two vectors (including the inverse) resp.~two arrays.

Special constructions:

transpositions.
 Todo:
 Now we know what a permutation is, we need a standard way of enumerating permutations.
Definition in file Permutations.hpp.