combinat-0.2.8.0: Generate and manipulate various combinatorial objects.

Safe Haskell None Haskell2010

Math.Combinat.Permutations

Description

Permutations.

See eg.: Donald E. Knuth: The Art of Computer Programming, vol 4, pre-fascicle 2B.

WARNING: As of version 0.2.8.0, I changed the convention of how permutations are represented internally. Also now they act on the right by default!

Synopsis

# The Permutation type

newtype Permutation Source

A permutation. Internally it is an (unboxed) array of the integers [1..n].

If this array of integers is [p1,p2,...,pn], then in two-line notations, that represents the permutation

( 1  2  3  ... n  )
( p1 p2 p3 ... pn )

That is, it is the permutation sigma whose (right) action on the set [1..n] is

sigma(1) = p1
sigma(2) = p2
...

(NOTE: this changed at version 0.2.8.0!)

Constructors

 Permutation (UArray Int Int)

Note: this is slower than permutationUArray

Note: Indexing starts from 1.

isPermutation :: [Int] -> Bool Source

Checks whether the input is a permutation of the numbers [1..n].

Checks whether the input is a permutation of the numbers [1..n].

Checks the input.

Assumes that the input is a permutation of the numbers [1..n].

Returns n, where the input is a permutation of the numbers [1..n]

# Disjoint cycles

newtype DisjointCycles Source

Disjoint cycle notation for permutations. Internally it is [[Int]].

The cycles are to be understood as follows: a cycle [c1,c2,...,ck] means the permutation

( c1 c2 c3 ... ck )
( c2 c3 c4 ... c1 )

Constructors

 DisjointCycles [[Int]]

Convert to disjoint cycle notation.

This is compatible with Maple's convert(perm,'disjcyc') and also with Mathematica's PermutationCycles[perm]

Note however, that for example Mathematica uses the top row to represent a permutation, while we use the bottom row - thus even though this function looks identical, the meaning of both the input and output is different!

# Queries

Checks whether the permutation is the identity permutation

Checks whether the permutation is the reverse permutation @[n,n-1,n-2,...,2,1].

Plus 1 or minus 1.

# Some concrete permutations

transposition :: Int -> (Int, Int) -> Permutation Source

A transposition (swapping two elements).

transposition n (i,j) is the permutation of size n which swaps i'th and j'th elements.

transpositions :: Int -> [(Int, Int)] -> Permutation Source

Product of transpositions.

transpositions n list == multiplyMany [ transposition n pair | pair <- list ]

adjacentTransposition n k swaps the elements k and (k+1).

Product of adjacent transpositions.

adjacentTranspositions n list == multiplyMany [ adjacentTransposition n idx | idx <- list ]

The permutation which cycles a list left by one step:

permuteList (cycleLeft 5) "abcde" == "bcdea"

Or in two-line notation:

( 1 2 3 4 5 )
( 2 3 4 5 1 )

The permutation which cycles a list right by one step:

permuteList (cycleRight 5) "abcde" == "eabcd"

Or in two-line notation:

( 1 2 3 4 5 )
( 5 1 2 3 4 )

The permutation [n,n-1,n-2,...,2,1]. Note that it is the inverse of itself.

# Permutation groups

The identity (or trivial) permutation.

The inverse permutation.

multiply :: Permutation -> Permutation -> Permutation infixr 7 Source

Multiplies two permutations together: p multiply q means the permutation when we first apply p, and then q (that is, the natural action is the right action)

See also permute for our conventions.

Multiply together a non-empty list of permutations (the reason for requiring the list to be non-empty is that we don't know the size of the result). See also multiplyMany'.

Multiply together a (possibly empty) list of permutations, all of which has size n

# Action of the permutation group

permute :: IArray arr b => Permutation -> arr Int b -> arr Int b Source

Right action of a permutation on a set. If our permutation is encoded with the sequence [p1,p2,...,pn], then in the two-line notation we have

( 1  2  3  ... n  )
( p1 p2 p3 ... pn )

We adopt the convention that permutations act on the right (as in Knuth):

permute pi2 (permute pi1 set) == permute (pi1 multiply pi2) set

Synonym to permuteRight

permuteList :: Permutation -> [a] -> [a] Source

Right action on lists. Synonym to permuteListRight

permuteLeft :: IArray arr b => Permutation -> arr Int b -> arr Int b Source

The left (opposite) action of the permutation group.

permuteLeft pi2 (permuteLeft pi1 set) == permuteLeft (pi2 multiply pi1) set

It is related to permuteLeft via:

permuteLeft  pi arr == permuteRight (inverse pi) arr
permuteRight pi arr == permuteLeft  (inverse pi) arr

permuteRight :: IArray arr b => Permutation -> arr Int b -> arr Int b Source

The right (standard) action of permutations on sets.

permuteRight pi2 (permuteRight pi1 set) == permuteRight (pi1 multiply pi2) set

The second argument should be an array with bounds (1,n). The function checks the array bounds.

permuteLeftList :: forall a. Permutation -> [a] -> [a] Source

The left (opposite) action on a list. The list should be of length n.

permuteLeftList perm set == permuteList (inverse perm) set
fromPermutation (inverse perm) == permuteLeftList perm [1..n]

permuteRightList :: forall a. Permutation -> [a] -> [a] Source

The right (standard) action on a list. The list should be of length n.

fromPermutation perm == permuteRightList perm [1..n]

# ASCII drawing

Synonym for twoLineNotation

The standard two-line notation, moving the element indexed by the top row into the place indexed by the corresponding element in the bottom row.

# List of permutations

A synonym for permutationsNaive

All permutations of [1..n] in lexicographic order, naive algorithm.

# = n!

# Random permutations

randomPermutation :: RandomGen g => Int -> g -> (Permutation, g) Source

A synonym for randomPermutationDurstenfeld.

_randomPermutation :: RandomGen g => Int -> g -> ([Int], g) Source

randomCyclicPermutation :: RandomGen g => Int -> g -> (Permutation, g) Source

A synonym for randomCyclicPermutationSattolo.

randomPermutationDurstenfeld :: RandomGen g => Int -> g -> (Permutation, g) Source

Generates a uniformly random permutation of [1..n]. Durstenfeld's algorithm (see http://en.wikipedia.org/wiki/Knuth_shuffle).

randomCyclicPermutationSattolo :: RandomGen g => Int -> g -> (Permutation, g) Source

Generates a uniformly random cyclic permutation of [1..n]. Sattolo's algorithm (see http://en.wikipedia.org/wiki/Knuth_shuffle).

# Multisets

permuteMultiset :: (Eq a, Ord a) => [a] -> [[a]] Source

Generates all permutations of a multiset. The order is lexicographic. A synonym for fasc2B_algorithm_L

countPermuteMultiset :: (Eq a, Ord a) => [a] -> Integer Source

# = \frac { (sum_i n_i) ! } { \prod_i (n_i !) }

fasc2B_algorithm_L :: (Eq a, Ord a) => [a] -> [[a]] Source

Generates all permutations of a multiset (based on "algorithm L" in Knuth; somewhat less efficient). The order is lexicographic.