Maintainer | Anders Claesson <anders.claesson@gmail.com> |
---|---|
Safe Haskell | None |
Common permutation statistics. Please contact the maintainer if you feel that there is a statistic that is missing; even better, send a patch or make a pull request.
To avoid name clashes this module is best imported qualified
;
e.g.
import qualified Math.Sym.Stat as S
For any permutation statistic f
, below, it holds that f w == f
(st w)
, and therefore the explanations below will be done on
standard permutations for convenience.
- asc :: Perm a => a -> Int
- des :: Perm a => a -> Int
- exc :: Perm a => a -> Int
- fp :: Perm a => a -> Int
- cyc :: Perm a => a -> Int
- inv :: Perm a => a -> Int
- maj :: Perm a => a -> Int
- comaj :: Perm a => a -> Int
- peak :: Perm a => a -> Int
- vall :: Perm a => a -> Int
- dasc :: Perm a => a -> Int
- ddes :: Perm a => a -> Int
- lmin :: Perm a => a -> Int
- lmax :: Perm a => a -> Int
- rmin :: Perm a => a -> Int
- rmax :: Perm a => a -> Int
- head :: Perm a => a -> Int
- last :: Perm a => a -> Int
- lir :: Perm a => a -> Int
- ldr :: Perm a => a -> Int
- rir :: Perm a => a -> Int
- rdr :: Perm a => a -> Int
- comp :: Perm a => a -> Int
- scomp :: Perm a => a -> Int
- ep :: Perm a => a -> Int
- dim :: Perm a => a -> Int
- asc0 :: Perm a => a -> Int
- des0 :: Perm a => a -> Int
- shad :: Perm a => a -> Int
Documentation
asc :: Perm a => a -> IntSource
The number of ascents. An ascent in w
is an index i
such
that w[i] < w[i+1]
.
des :: Perm a => a -> IntSource
The number of descents. A descent in w
is an index i
such
that w[i] > w[i+1]
.
cyc :: Perm a => a -> IntSource
The number of cycles: orbits of the permutation when viewed as a function.
inv :: Perm a => a -> IntSource
The number of inversions: pairs (i,j)
such that i < j
and w[i] > w[j]
.
peak :: Perm a => a -> IntSource
The number of peaks: positions i
such that w[i-1] < w[i]
and w[i] > w[i+1]
.
vall :: Perm a => a -> IntSource
The number of valleys: positions i
such that w[i-1] > w[i]
and w[i] < w[i+1]
.
dasc :: Perm a => a -> IntSource
The number of double ascents: positions i
such that w[i-1] < w[i] < w[i+1]
.
ddes :: Perm a => a -> IntSource
The number of double descents: positions i
such that w[i-1] > w[i] > w[i+1]
.
lmin :: Perm a => a -> IntSource
The number of left-to-right minima: positions i
such that w[i] < w[j]
for all j < i
.
lmax :: Perm a => a -> IntSource
The number of left-to-right maxima: positions i
such that w[i] > w[j]
for all j < i
.
rmin :: Perm a => a -> IntSource
The number of right-to-left minima: positions i
such that w[i] < w[j]
for all j > i
.
rmax :: Perm a => a -> IntSource
The number of right-to-left maxima: positions i
such that w[i] > w[j]
for all j > i
.
head :: Perm a => a -> IntSource
The first (left-most) element in the standardization. E.g., head "231" = head (fromList [1,2,0]) = 1
.
last :: Perm a => a -> IntSource
The last (right-most) element in the standardization. E.g., last "231" = last (fromList [1,2,0]) = 0
.
lir :: Perm a => a -> IntSource
Length of the left-most increasing run: largest i
such that
w[0] < w[1] < ... < w[i-1]
.
ldr :: Perm a => a -> IntSource
Length of the left-most decreasing run: largest i
such that
w[0] > w[1] > ... > w[i-1]
.
rir :: Perm a => a -> IntSource
Length of the right-most increasing run: largest i
such that
w[n-i] < ... < w[n-2] < w[n-1]
.
rdr :: Perm a => a -> IntSource
Length of the right-most decreasing run: largest i
such that
w[n-i] > ... > w[n-2] > w[n-1]
.
comp :: Perm a => a -> IntSource
The number of components. E.g., [2,0,3,1,4,6,7,5]
has three
components: [2,0,3,1]
, [4]
and [6,7,5]
.
scomp :: Perm a => a -> IntSource
The number of skew components. E.g., [5,7,4,6,3,1,0,2]
has three
skew components: [5,7,4,6]
, [3]
and [1,0,2]
.
ep :: Perm a => a -> IntSource
The rank as defined by Elizalde and Pak [Bijections for refined restricted permutations, J. Comb. Theory, Ser. A, 2004]:
maximum [ k | k <- [0..n-1], w[i] >= k for all i < k ]
dim :: Perm a => a -> IntSource
The dimension of a permutation is defined as the largest non-fixed-point, or zero if all points are fixed.
asc0 :: Perm a => a -> IntSource
The number of small ascents. A small ascent in w
is an index
i
such that w[i] + 1 == w[i+1]
.