sym-0.8: 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

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

inflate :: Perm0 -> [Perm0] -> Perm0Source

`inflate w vs` is the inflation of `w` by `vs`.

`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 co-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 left-to-right minima.

The number of left-to-right 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.

The number of skew 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.

# Left-to-right maxima, etc

The set of indices of left-to-right maxima.

The set of indices of right-to-left maxima.

# Components

The set of indices of components.

# 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

# Bijections

The Simion-Schmidt bijection from Av(123) onto Av(132).

The inverse of the Simion-Schmidt bijection. It is a function from Av(132) to Av(123).

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