Maintainer | Anders Claesson <anders.claesson@gmail.com> |
---|---|

Safe Haskell | None |

- class Ord a => Permutation a where
- perms :: Permutation a => Int -> [a]
- lift :: Permutation a => (Perm -> Perm) -> a -> a
- lift2 :: Permutation a => (Perm -> Perm -> Perm) -> a -> a -> a

# Documentation

class Ord a => Permutation a whereSource

The class of permutations. Minimal complete definition: `st`

,
`act`

and `idperm`

. The default implementation of `size`

can be
somewhat slow, so you may want to implement it as well.

The standardization map. If there is an underlying linear
order on `a`

then `st`

is determined by the unique order
preserving map from `[0..]`

to that order. In any case, the
standardization map should be equivariant with respect to the
group action defined below; i.e., it should hold that

st (u `act` v) == u `act` st v

A (left) *group action* of `Perm`

on `a`

. As for any group
action it should hold that

(u `act` v) `act` w == u `act` (v `act` w) && idperm n `act` v == v

where `v,w::a`

and `u::Perm`

are of size `n`

.

The size of a permutation. The default implementation derived from

size == size . st

This is not a circular definition as `size`

on `Perm`

is
implemented independently. If the implementation of `st`

is
slow, then it can be worth while to override the standard
definiton; any implementation should, however, satisfy the
identity above.

The identity permutation of the given size.

The group theoretical inverse. It should hold that

inverse == unst . inverse . st

and this is the default implementation.

ordiso :: Perm -> a -> BoolSource

Predicate determining if two permutations are order-isomorphic. The default implementation uses

u `ordiso` v == u == st v

Equivalently, one could use

u `ordiso` v == inverse u `act` v == idperm (size u)

unst :: Permutation a => Perm -> aSource

The inverse of `st`

. It should hold that

unst w == w `act` idperm (P.size w)

and this is the default implementation.

Permutation String | A String viewed as a permutation of its characters. The alphabet is ordered as ['1'..'9'] ++ ['A'..'Z'] ++ ['a'..] |

Permutation Perm |

perms :: Permutation a => Int -> [a]Source

The list of all permutations of the given size.