sym-0.2.3: Permutations, patterns, and statistics

Maintainer Anders Claesson None

Math.Sym.Internal

Description

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.

Synopsis

# Documentation

A Lehmercode is a vector of integers `w` such `w!i <= length w - 1 - i` for each `i` in `[0..length w - 1]`.

type Perm0 = Vector IntSource

By convention, a member of `Perm0` is a permutation of some finite subset of `[0..]`.

# Lehmercodes

`unrankLehmercode n rank` is the `rank`-th Lehmercode of length `n`.

Build a permutation from its Lehmercode.

A random Lehmercode of the given length.

The list of Lehmercodes of a given length.

# Permutations

The size of a permutation; the number of elements.

toList :: Perm0 -> [Int]Source

The list of images of a permutation.

fromList :: [Int] -> Perm0Source

Make a permutation from a list of images.

act :: Perm0 -> Perm0 -> Perm0Source

`act u v` is the permutation w defined by w(u(i)) = v(i).

`unrankPerm n rank` is the `rank`-th (Myrvold & Ruskey) permutation of length `n`.

A random permutation of the given length.

sym :: Int -> [Perm0]Source

`sym n` is the list of permutations of `[0..n-1]` (the symmetric group).

The identity permutation of the given length.

The reverse of the identity permutation.

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

The standardization map.

`ordiso u v m` determines whether the subword in `v` specified by `m` is order isomorphic to `u`.

`simple w` determines whether `w` is simple

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 <a_1,...,a_n> == <a_n,,...,a_1>`. E.g., ```reverse <9,3,7,2> == <2,7,3,9>```.

`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 w` is the group theoretical inverse of `w`. E.g., `inverse <1,2,0> == <2,0,1>`.

The clockwise rotatation through 90 degrees. E.g., `rotate <1,0,2> == <1,2,0>`.

# Permutation statistics

The number of ascents.

The number of descents.

The number of excedances.

fp :: Perm0 -> IntSource

The number of fixed points.

The number of cycles.

The number of inversions.

The major index.

The number of peaks.

The number of valleys.

The number of double ascents.

The number of double descents.

The number of left-to-right minima.

The number of left-to-right maxima.

The number of right-to-left minima.

The number of right-to-left maxima.

First (left-most) value of a permutation.

Last (right-most) value of a permutation.

The left-most increasing run.

The left-most decreasing run.

The right-most increasing run.

The right-most decreasing run.

The number of components.

ep :: Perm0 -> IntSource

Rank as defined by Elizalde & Pak.

Dimension (largest non-fixed-point).

The number of small ascents.

The number of small descents.

# List valued permutation statistics

The list of values of left-to-right minima

The list of indices of left-to-right minima

# Sorting operators

One pass of stack-sort.

One pass of bubble-sort.

# Single point deletions

del :: Int -> Perm0 -> Perm0Source

Delete the element at a given position

`onesCUInt k m` gives the `k` smallest indices whose bits are set in `m`.
Lexicographically, the next `CUInt` with the same Hamming weight.