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
- 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]
- 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
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
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]