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

Safe Haskell | None |

- data StPerm
- empty :: StPerm
- one :: StPerm
- toVector :: StPerm -> Vector Int
- fromVector :: Vector Int -> StPerm
- toList :: StPerm -> [Int]
- fromList :: [Int] -> StPerm
- (/-/) :: StPerm -> StPerm -> StPerm
- bijection :: StPerm -> Int -> Int
- unrankStPerm :: Int -> Integer -> StPerm
- sym :: Int -> [StPerm]
- class Perm a where
- generalize :: Perm a => (StPerm -> StPerm) -> a -> a
- normalize :: (Ord a, Perm a) => [a] -> [a]
- cast :: (Perm a, Perm b) => a -> b
- unrankPerm :: Perm a => Int -> Integer -> a
- randomPerm :: Perm a => Int -> IO a
- perms :: Perm a => Int -> [a]
- stackSort :: Perm a => a -> a
- bubbleSort :: Perm a => a -> a
- copiesOf :: Perm a => StPerm -> a -> [Set]
- avoids :: Perm a => a -> [StPerm] -> Bool
- avoiders :: Perm a => [StPerm] -> [a] -> [a]
- av :: [StPerm] -> Int -> [StPerm]
- del :: Perm a => Int -> a -> a
- shadow :: (Ord a, Perm a) => [a] -> [a]
- downset :: (Ord a, Perm a) => [a] -> [a]
- ext :: Perm a => Int -> a -> a
- coshadow :: (Ord a, Perm a) => [a] -> [a]
- lMaxima :: Perm a => a -> Set
- lMinima :: Perm a => a -> Set
- rMaxima :: Perm a => a -> Set
- rMinima :: Perm a => a -> Set
- components :: Perm a => a -> Set
- skewComponents :: Perm a => a -> Set
- simple :: Perm a => a -> Bool
- 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`

`act`

and `idperm`

. The default implementations of `size`

and
`neutralize`

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) && neutralize 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 of the given size.

neutralize :: a -> aSource

The permutation obtained by acting on the given permutation with its own inverse; that is, the identity permutation on the same underlying set as the given permutation. It should hold that

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

The default implementation uses the last of these three equations.

The group theoretical inverse. It should hold that

inverse u == inverse (st u) `act` neutralize 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 == neutralize v

# Generalize, normalize and cast

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` neutralize v

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

is size preserving.

normalize :: (Ord a, Perm a) => [a] -> [a]Source

Sort a list of permutations with respect to the standardization and remove duplicates

# Generating permutations

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

`unrankPerm u rank`

is the `rank`

-th (Myrvold & Ruskey)
permutation of size `n`

. E.g.,

unrankPerm 9 88888 == "561297843"

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

`randomPerm n`

is a random permutation of size `n`

.

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

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

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

# Sorting operators

bubbleSort :: Perm a => a -> aSource

One pass of bubble-sort.

# Permutation patterns

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

`copiesOf p w`

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

in the permutation `w`

. E.g.,

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

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

`avoids w ps`

is a predicate determining if `w`

avoids the patterns `ps`

.

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

`avoiders ps vs`

is the list of permutations in `vs`

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]

# Single point extensions/deletions, shadows and downsets

downset :: (Ord a, Perm a) => [a] -> [a]Source

The list of permutations that are contained in at least one of the given permutaions

ext :: Perm a => Int -> a -> aSource

Extend a permutation by inserting a new largest element at the given position

# Left-to-right maxima and similar functions

# Components and skew components

components :: Perm a => a -> SetSource

The set of indices of components.

skewComponents :: Perm a => a -> SetSource

The set of indices of skew components.