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
- bijection :: StPerm -> Int -> Int
- unrankStPerm :: Int -> Integer -> StPerm
- sym :: Int -> [StPerm]
- class Perm a where
- generalize :: Perm a => (StPerm -> StPerm) -> 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]
- 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
- 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
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.
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 and deletions
ext :: Perm a => Int -> a -> aSource
Extend a permutation by inserting a new largest element at the given position