sym-0.1: Permutations, patterns, and statistics

Maintainer Anders Claesson Safe-Infered

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

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

# Sorting operators

One pass of stack-sort.

One pass of bubble-sort.

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