Maintainer | Anders Claesson <anders.claesson@gmail.com> |
---|---|
Safe Haskell | None |
An internal module used by the sym package.
A Lehmercode is a vector of integers w
such w!i <= length w - 1 - i
for each i
in [0..length w - 1]
; such a vector encodes a permutation.
This module implements O(n) algorithms for unranking Lehmercodes and
permutations; the algorithms are due to W. Myrvold and F. Ruskey
[Ranking and Unranking Permutations in Linear Time, Information Processing
Letters, 79 (2001) 281-284].
In addition, this module implements sorting operators, the symmetries in D8 acting on permutations, as well as most of the common permutation statistics.
- type Lehmercode = Vector Int
- type Perm0 = Vector Int
- unrankLehmercode :: Int -> Integer -> Lehmercode
- fromLehmercode :: Lehmercode -> Perm0
- randomLehmercode :: Int -> IO Lehmercode
- lehmercodes :: Int -> [Lehmercode]
- size :: Perm0 -> Int
- toList :: Perm0 -> [Int]
- fromList :: [Int] -> Perm0
- act :: Perm0 -> Perm0 -> Perm0
- unrankPerm :: Int -> Integer -> Perm0
- randomPerm :: Int -> IO Perm0
- sym :: Int -> [Perm0]
- idperm :: Int -> Perm0
- revIdperm :: Int -> Perm0
- sti :: Perm0 -> Perm0
- st :: Perm0 -> Perm0
- ordiso :: Perm0 -> Perm0 -> Vector Int -> Bool
- simple :: Perm0 -> Bool
- copies :: (Int -> Int -> [Vector Int]) -> Perm0 -> Perm0 -> [Vector Int]
- avoiders :: (Int -> Int -> [Vector Int]) -> (a -> Perm0) -> [Perm0] -> [a] -> [a]
- reverse :: Perm0 -> Perm0
- complement :: Perm0 -> Perm0
- inverse :: Perm0 -> Perm0
- rotate :: Perm0 -> Perm0
- asc :: Perm0 -> Int
- des :: Perm0 -> Int
- exc :: Perm0 -> Int
- fp :: Perm0 -> Int
- cyc :: Perm0 -> Int
- inv :: Perm0 -> Int
- maj :: Perm0 -> Int
- comaj :: Perm0 -> Int
- peak :: Perm0 -> Int
- vall :: Perm0 -> Int
- dasc :: Perm0 -> Int
- ddes :: Perm0 -> Int
- lmin :: Perm0 -> Int
- lmax :: Perm0 -> Int
- rmin :: Perm0 -> Int
- rmax :: Perm0 -> Int
- head :: Perm0 -> Int
- last :: Perm0 -> Int
- lir :: Perm0 -> Int
- ldr :: Perm0 -> Int
- rir :: Perm0 -> Int
- rdr :: Perm0 -> Int
- comp :: Perm0 -> Int
- ep :: Perm0 -> Int
- dim :: Perm0 -> Int
- asc0 :: Perm0 -> Int
- des0 :: Perm0 -> Int
- lminValues :: Perm0 -> Vector Int
- lminIndices :: Perm0 -> Vector Int
- stackSort :: Perm0 -> Perm0
- bubbleSort :: Perm0 -> Perm0
- del :: Int -> Perm0 -> Perm0
- onesCUInt :: CUInt -> Vector Int
- nextCUInt :: CUInt -> CUInt
- nextIntegral :: (Integral a, Bits a) => a -> a
Documentation
type Lehmercode = Vector IntSource
A Lehmercode is a vector of integers w
such w!i <= length w - 1 - i
for each i
in [0..length w - 1]
.
By convention, a member of Perm0
is a permutation of some
finite subset of [0..]
.
Lehmercodes
unrankLehmercode :: Int -> Integer -> LehmercodeSource
unrankLehmercode n rank
is the rank
-th Lehmercode of length n
.
fromLehmercode :: Lehmercode -> Perm0Source
Build a permutation from its Lehmercode.
randomLehmercode :: Int -> IO LehmercodeSource
A random Lehmercode of the given length.
lehmercodes :: Int -> [Lehmercode]Source
The list of Lehmercodes of a given length.
Permutations
unrankPerm :: Int -> Integer -> Perm0Source
unrankPerm n rank
is the rank
-th (Myrvold & Ruskey) permutation of length n
.
randomPerm :: Int -> IO Perm0Source
A random permutation of the given length.
sti w
is the inverse of the standardization of w
(a
permutation on [0..length w-1]
). E.g., sti <4,9,2> ==
<2,0,1>
.
ordiso :: Perm0 -> Perm0 -> Vector Int -> BoolSource
ordiso u v m
determines whether the subword in v
specified by
m
is order isomorphic to u
.
copies :: (Int -> Int -> [Vector Int]) -> Perm0 -> Perm0 -> [Vector Int]Source
copies subsets p w
is the list of bitmasks that represent copies of p
in w
.
avoiders :: (Int -> Int -> [Vector Int]) -> (a -> Perm0) -> [Perm0] -> [a] -> [a]Source
avoiders subsets st ps ws
is the list of permutations in ws
avoiding the patterns in ps
.
Permutation symmetries
reverse :: Perm0 -> Perm0Source
reverse <a_1,...,a_n> == <a_n,,...,a_1>
. E.g., reverse
<9,3,7,2> == <2,7,3,9>
.
complement :: Perm0 -> Perm0Source
complement <a_1,...,a_n> == <b_1,,...,b_n>
, where b_i = n - a_i - 1
.
E.g., complement <3,4,0,1,2> == <1,0,4,3,2>
.
inverse :: Perm0 -> Perm0Source
inverse w
is the group theoretical inverse of w
. E.g.,
inverse <1,2,0> == <2,0,1>
.
rotate :: Perm0 -> Perm0Source
The clockwise rotatation through 90 degrees. E.g.,
rotate <1,0,2> == <1,2,0>
.
Permutation statistics
List valued permutation statistics
lminValues :: Perm0 -> Vector IntSource
The list of values of left-to-right minima
lminIndices :: Perm0 -> Vector IntSource
The list of indices of left-to-right minima
Sorting operators
bubbleSort :: Perm0 -> Perm0Source
One pass of bubble-sort.
Single point deletions
Bitmasks
onesCUInt :: CUInt -> Vector IntSource
onesCUInt k m
gives the k
smallest indices whose bits are set in m
.
nextIntegral :: (Integral a, Bits a) => a -> aSource
Lexicographically, the next integral number with the same Hamming weight.