Maintainer | Anders Claesson <anders.claesson@gmail.com> |
---|---|
Safe Haskell | None |
- Standard permutations
- The permutation typeclass
- Convenience functions
- Constructions
- Generating permutations
- Sorting operators
- Permutation patterns
- Single point extensions/deletions, shadows and downsets
- Left-to-right maxima and similar functions
- Components and skew components
- Simple permutations
- Subsets
- data StPerm
- toList :: StPerm -> [Int]
- fromList :: [Int] -> StPerm
- sym :: Int -> [StPerm]
- class Perm a where
- empty :: Perm a => a
- one :: Perm a => a
- toVector :: Perm a => a -> Vector Int
- fromVector :: Perm a => Vector Int -> a
- bijection :: StPerm -> Int -> Int
- generalize :: (Perm a, Perm b) => (StPerm -> StPerm) -> a -> b
- generalize2 :: (Perm a, Perm b, Perm c) => (StPerm -> StPerm -> StPerm) -> a -> b -> c
- normalize :: (Ord a, Perm a) => [a] -> [a]
- cast :: (Perm a, Perm b) => a -> b
- (\+\) :: Perm a => a -> a -> a
- dsum :: Perm a => [a] -> a
- (/-/) :: Perm a => a -> a -> a
- ssum :: Perm a => [a] -> a
- inflate :: Perm a => a -> [a] -> a
- 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]
.
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.
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.
The group theoretical inverse. It should hold that
inverse == unst . inverse . st
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 (size u)
unstn :: Int -> StPerm -> aSource
The inverse of the standardization function. For efficiency reasons we make the size of the permutation an argument to this function. It should hold that
unst n w == w `act` idperm n
and this is the default implementation. An un-standardization
function without the size argument is given by unst
below.
unst :: Perm a => StPerm -> aSource
The inverse of st
. It should hold that
unst w == unstn (size w) w
and this is the default implementation.
Convenience functions
fromVector :: Perm a => Vector Int -> aSource
Convert a vector to a permutation. The vector should be a
permutation of the elements [0..k-1]
for some positive k
. No
checks for this are done.
generalize :: (Perm a, Perm b) => (StPerm -> StPerm) -> a -> bSource
Generalize a function on StPerm
to a function on any permutations:
generalize f = unst . f . st
generalize2 :: (Perm a, Perm b, Perm c) => (StPerm -> StPerm -> StPerm) -> a -> b -> cSource
Like generalize
but for functions of two variables
normalize :: (Ord a, Perm a) => [a] -> [a]Source
Sort a list of permutations with respect to the standardization and remove duplicates
Constructions
inflate :: Perm a => a -> [a] -> aSource
inflate w vs
is the inflation of w
by vs
. It is the
permutation of length sum (map size vs)
obtained by replacing
each entry w!i
by an interval that is order isomorphic to vs!i
in such a way that the intervals are order isomorphic to w
. In
particular,
u \+\ v == inflate (fromList [0,1]) [u,v] u /-/ v == inflate (fromList [1,0]) [u,v]
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.