Maintainer | Anders Claesson <anders.claesson@gmail.com> |
---|---|

Safe Haskell | None |

Common permutation statistics. To avoid name clashes this module is
best imported `qualified`

; e.g.

import qualified Math.Perm.Stat as S

- asc :: Perm -> Int
- des :: Perm -> Int
- exc :: Perm -> Int
- fp :: Perm -> Int
- sfp :: Perm -> Int
- cyc :: Perm -> Int
- inv :: Perm -> Int
- maj :: Perm -> Int
- comaj :: Perm -> Int
- peak :: Perm -> Int
- vall :: Perm -> Int
- dasc :: Perm -> Int
- ddes :: Perm -> Int
- lmin :: Perm -> Int
- lmax :: Perm -> Int
- rmin :: Perm -> Int
- rmax :: Perm -> Int
- head :: Perm -> Int
- last :: Perm -> Int
- lir :: Perm -> Int
- ldr :: Perm -> Int
- rir :: Perm -> Int
- rdr :: Perm -> Int
- comp :: Perm -> Int
- scomp :: Perm -> Int
- ep :: Perm -> Int
- dim :: Perm -> Int
- asc0 :: Perm -> Int
- des0 :: Perm -> Int

# Documentation

The number of ascents. An *ascent* in `w`

is an index `i`

such
that `w[i] < w[i+1]`

.

The number of descents. A *descent* in `w`

is an index `i`

such
that `w[i] > w[i+1]`

.

The number of *strong fixed points* (also called splitters):
positions `i`

such that `w[j] < i`

for `j < i`

and `w[j] > i`

for `j > i`

.

The number of *peaks*:
positions `i`

such that `w[i-1] < w[i]`

and `w[i] > w[i+1]`

.

The number of *valleys*:
positions `i`

such that `w[i-1] > w[i]`

and `w[i] < w[i+1]`

.

The number of *double ascents*:
positions `i`

such that `w[i-1] < w[i] < w[i+1]`

.

The number of *double descents*:
positions `i`

such that `w[i-1] > w[i] > w[i+1]`

.

The number of *left-to-right minima*:
positions `i`

such that `w[i] < w[j]`

for all `j < i`

.

The number of *left-to-right maxima*:
positions `i`

such that `w[i] > w[j]`

for all `j < i`

.

The number of *right-to-left minima*:
positions `i`

such that `w[i] < w[j]`

for all `j > i`

.

The number of *right-to-left maxima*:
positions `i`

such that `w[i] > w[j]`

for all `j > i`

.

The first (left-most) element in the standardization. E.g.,
`head "231" = head (fromList [1,2,0]) = 1`

.

The last (right-most) element in the standardization. E.g.,
`last "231" = last (fromList [1,2,0]) = 0`

.

Length of the left-most increasing run: largest `i`

such that
`w[0] < w[1] < ... < w[i-1]`

.

Length of the left-most decreasing run: largest `i`

such that
`w[0] > w[1] > ... > w[i-1]`

.

Length of the right-most increasing run: largest `i`

such that
`w[n-i] < ... < w[n-2] < w[n-1]`

.

Length of the right-most decreasing run: largest `i`

such that
`w[n-i] > ... > w[n-2] > w[n-1]`

.

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

.

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

.

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 ]

The dimension of a permutation is defined as the largest non-fixed-point, or zero if all points are fixed.

The number of small ascents. A *small ascent* in `w`

is an index
`i`

such that `w[i] + 1 == w[i+1]`

.