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

Safe Haskell | None |

- data StPerm
- toVector :: StPerm -> Vector Int
- fromVector :: Vector Int -> StPerm
- toList :: StPerm -> [Int]
- fromList :: [Int] -> StPerm
- (/-/) :: StPerm -> StPerm -> StPerm
- unrankStPerm :: Int -> Integer -> StPerm
- sym :: Int -> [StPerm]
- class Perm a where
- generalize :: Perm a => (StPerm -> StPerm) -> a -> a
- unrankPerm :: Perm a => a -> Integer -> a
- randomPerm :: Perm a => a -> IO a
- perms :: Perm a => a -> [a]
- stackSort :: Perm a => a -> a
- bubbleSort :: Perm a => a -> a
- copies :: Perm a => StPerm -> a -> [Set]
- avoids :: Perm a => [StPerm] -> a -> Bool
- avoiders :: Perm a => [StPerm] -> [a] -> [a]
- av :: [StPerm] -> Int -> [StPerm]
- type Set = Vector Int
- subsets :: Int -> Int -> [Set]

# Standard permutations

By a *standard permutation* we shall mean a permutations of
`[0..k-1]`

.

fromVector :: Vector Int -> StPermSource

Convert a vector to a standard permutation. The vector should be a
permutation of the elements `[0..k-1]`

for some positive `k`

. No
checks for this are done.

fromList :: [Int] -> StPermSource

Convert a list to a standard permutation. The list should a
permutation of the elements `[0..k-1]`

for some positive `k`

. No
checks for this are done.

unrankStPerm :: Int -> Integer -> StPermSource

`unrankStPerm n rank`

is the `rank`

-th (Myrvold & Ruskey)
permutation of `[0..n-1]`

. E.g.,

unrankStPerm 16 19028390 == fromList [6,15,4,11,7,8,9,2,5,0,10,3,12,13,14,1]

The list of standard permutations of the given size (the symmetric group). E.g.,

sym 2 == [fromList [0,1], fromList [1,0]]

# The permutation typeclass

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

and
`act`

. The default implementations of `size`

and `idperm`

can be
somewhat slow, so you may want to implement them 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 `StPerm`

on `a`

. As for any group
action it should hold that

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

The size of a permutation. The default implementation derived from

size == size . st

This is not a circular definition as `size`

on `StPerm`

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 on the same underlying set as the given permutation. It should hold that

st (idperm u) == idperm (st u)

Group theoretically, it should also hold that ```
u . inverse u ==
idperm u
```

. In terms of the group action this means

idperm u == inverse (st u) `act` u

and this is the default implementation.

The group theoretical inverse. It should hold that

inverse u == inverse (st u) `act` idperm u

and this is the default implementation.

ordiso :: StPerm -> 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 v

# Generalize

generalize :: Perm a => (StPerm -> StPerm) -> a -> aSource

Generalize a function on `StPerm`

to a function on any permutations:

generalize f v = f (st v) `act` idperm v

Note that this will only work as intended if `f`

is size preserving.

# Generating permutations

unrankPerm :: Perm a => a -> Integer -> aSource

`unrankPerm u rank`

is the `rank`

-th (Myrvold & Ruskey)
permutation of `u`

. E.g.,

unrankPerm ['1'..'9'] 88888 == "561297843"

randomPerm :: Perm a => a -> IO aSource

`randomPerm u`

is a random permutation of `u`

.

perms :: Perm a => a -> [a]Source

All permutations of a given permutation. E.g.,

perms "123" == ["123","213","321","132","231","312"]

# Sorting operators

bubbleSort :: Perm a => a -> aSource

One pass of bubble-sort.

# Permutation patterns

copies :: Perm a => StPerm -> a -> [Set]Source

`copies p w`

is the list of (indices of) copies of the pattern
`p`

in the permutation `w`

. E.g.,

copies (st "21") "2431" == [fromList [1,2],fromList [0,3],fromList [1,3],fromList [2,3]]

avoids :: Perm a => [StPerm] -> a -> BoolSource

`avoids ps w`

is a predicate determining if `w`

avoids the patterns `ps`

.

avoiders :: Perm a => [StPerm] -> [a] -> [a]Source

`avoiders ps v`

is the list of permutations of `v`

avoiding the
patterns `ps`

. This is equivalent to the definition

avoiders ps = filter (avoids ps)

but is usually much faster.

av :: [StPerm] -> Int -> [StPerm]Source

`av ps n`

is the list of permutations of `[0..n-1]`

avoiding the
patterns `ps`

. E.g.,

map (length . av [st "132", st "321"]) [1..8] == [1,2,4,7,11,16,22,29]