Math.Combinat.Permutations

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!

The Permutation type

newtype Permutation

A permutation. Internally it is an (compact) vector 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 WordVec

Instances

Read Permutation

Defined in Math.Combinat.Permutations

Methods

readsPrec :: Int -> ReadS Permutation

readList :: ReadS [Permutation]

readPrec :: ReadPrec Permutation

readListPrec :: ReadPrec [Permutation]

Show Permutation

Defined in Math.Combinat.Permutations

Methods

showsPrec :: Int -> Permutation -> ShowS

show :: Permutation -> String

showList :: [Permutation] -> ShowS

DrawASCII Permutation

Defined in Math.Combinat.Permutations

Methods

ascii :: Permutation -> ASCII

HasNumberOfCycles Permutation

Defined in Math.Combinat.Permutations

Methods

numberOfCycles :: Permutation -> Int

HasWidth Permutation

Defined in Math.Combinat.Permutations

Methods

width :: Permutation -> Int

Eq Permutation

Defined in Math.Combinat.Permutations

Methods

(==) :: Permutation -> Permutation -> Bool

(/=) :: Permutation -> Permutation -> Bool

Ord Permutation

Defined in Math.Combinat.Permutations

Methods

compare :: Permutation -> Permutation -> Ordering

(<) :: Permutation -> Permutation -> Bool

(<=) :: Permutation -> Permutation -> Bool

(>) :: Permutation -> Permutation -> Bool

(>=) :: Permutation -> Permutation -> Bool

max :: Permutation -> Permutation -> Permutation

min :: Permutation -> Permutation -> Permutation

fromPermutation :: Permutation -> [Int]

lookupPermutation :: Permutation -> Int -> Int

Returns the image sigma(k) of k under the permutation sigma.

Note: we don't check the bounds! It may even crash if you index out of bounds!

(!!!) :: Permutation -> Int -> Int

Infix version of lookupPermutation

permutationArray :: Permutation -> Array Int Int

permutationUArray :: Permutation -> UArray Int Int

uarrayToPermutationUnsafe :: UArray Int Int -> Permutation

Note: Indexing starts from 1.

isPermutation :: [Int] -> Bool

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

maybePermutation :: [Int] -> Maybe Permutation

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

toPermutation :: [Int] -> Permutation

Checks the input.

toPermutationUnsafe :: [Int] -> Permutation

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

toPermutationUnsafeN :: Int -> [Int] -> Permutation

This is faster than toPermutationUnsafe, but you need to supply n.

permutationSize :: Permutation -> Int

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

Disjoint cycles

newtype DisjointCycles

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

Instances

Read DisjointCycles

Defined in Math.Combinat.Permutations

Methods

readsPrec :: Int -> ReadS DisjointCycles

readList :: ReadS [DisjointCycles]

readPrec :: ReadPrec DisjointCycles

readListPrec :: ReadPrec [DisjointCycles]

Show DisjointCycles

Defined in Math.Combinat.Permutations

Methods

showsPrec :: Int -> DisjointCycles -> ShowS

show :: DisjointCycles -> String

showList :: [DisjointCycles] -> ShowS

DrawASCII DisjointCycles

Defined in Math.Combinat.Permutations

Methods

ascii :: DisjointCycles -> ASCII

HasNumberOfCycles DisjointCycles

Defined in Math.Combinat.Permutations

Methods

numberOfCycles :: DisjointCycles -> Int

Eq DisjointCycles

Defined in Math.Combinat.Permutations

Methods

(==) :: DisjointCycles -> DisjointCycles -> Bool

(/=) :: DisjointCycles -> DisjointCycles -> Bool

Ord DisjointCycles

Defined in Math.Combinat.Permutations

Methods

compare :: DisjointCycles -> DisjointCycles -> Ordering

(<) :: DisjointCycles -> DisjointCycles -> Bool

(<=) :: DisjointCycles -> DisjointCycles -> Bool

(>) :: DisjointCycles -> DisjointCycles -> Bool

(>=) :: DisjointCycles -> DisjointCycles -> Bool

max :: DisjointCycles -> DisjointCycles -> DisjointCycles

min :: DisjointCycles -> DisjointCycles -> DisjointCycles

fromDisjointCycles :: DisjointCycles -> [[Int]]

disjointCyclesUnsafe :: [[Int]] -> DisjointCycles

permutationToDisjointCycles :: Permutation -> DisjointCycles

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!

disjointCyclesToPermutation :: Int -> DisjointCycles -> Permutation

numberOfCycles :: HasNumberOfCycles p => p -> Int

concatPermutations :: Permutation -> Permutation -> Permutation

Given a permutation of n and a permutation of m, we return a permutation of n+m resulting by putting them next to each other. This should satisfy

permuteList p1 xs ++ permuteList p2 ys == permuteList (concatPermutations p1 p2) (xs++ys)

Queries

isIdentityPermutation :: Permutation -> Bool

Checks whether the permutation is the identity permutation

isReversePermutation :: Permutation -> Bool

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

isEvenPermutation :: Permutation -> Bool

isOddPermutation :: Permutation -> Bool

signOfPermutation :: Permutation -> Sign

signValueOfPermutation :: Num a => Permutation -> a

Plus 1 or minus 1.

module Math.Combinat.Sign

isCyclicPermutation :: Permutation -> Bool

Some concrete permutations

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

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

Product of transpositions.

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

adjacentTransposition :: Int -> Int -> Permutation

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

adjacentTranspositions :: Int -> [Int] -> Permutation

Product of adjacent transpositions.

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

cycleLeft :: Int -> Permutation

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 )

cycleRight :: Int -> Permutation

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 )

reversePermutation :: Int -> Permutation

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

Inversions

inversions :: Permutation -> [(Int, Int)]

An inversion of a permutation sigma is a pair (i,j) such that i<j and sigma(i) > sigma(j).

This functions returns the inversion of a permutation.

numberOfInversions :: Permutation -> Int

Returns the number of inversions:

numberOfInversions perm = length (inversions perm)

Synonym for numberOfInversionsMerge

numberOfInversionsNaive :: Permutation -> Int

Returns the number of inversions, using the definition, thus it's O(n^2).

numberOfInversionsMerge :: Permutation -> Int

Returns the number of inversions, using the merge-sort algorithm. This should be O(n*log(n))

bubbleSort2 :: Permutation -> [(Int, Int)]

Bubble sorts breaks a permutation into the product of adjacent transpositions:

multiplyMany' n (map (transposition n) $ bubbleSort2 perm) == perm

Note that while this is not unique, the number of transpositions equals the number of inversions.

bubbleSort :: Permutation -> [Int]

Another version of bubble sort. An entry i in the return sequence means the transposition (i,i+1):

multiplyMany' n (map (adjacentTransposition n) $ bubbleSort perm) == perm

Permutation groups

identityPermutation :: Int -> Permutation

The identity (or trivial) permutation.

inversePermutation :: Permutation -> Permutation

The inverse permutation.

multiplyPermutation :: Permutation -> Permutation -> Permutation infixr 7

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

See also permuteArray for our conventions.

productOfPermutations :: [Permutation] -> Permutation

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

productOfPermutations' :: Int -> [Permutation] -> Permutation

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

Action of the permutation group

permuteArray :: IArray arr b => Permutation -> arr Int b -> arr Int b

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):

permuteArray pi2 (permuteArray pi1 set) == permuteArray (pi1 `multiplyPermutation` pi2) set

Synonym to permuteArrayRight

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

Right action on lists. Synonym to permuteListRight

permuteArrayLeft :: IArray arr b => Permutation -> arr Int b -> arr Int b

The left (opposite) action of the permutation group.

permuteArrayLeft pi2 (permuteArrayLeft pi1 set) == permuteArrayLeft (pi2 `multiplyPermutation` pi1) set

It is related to permuteLeftArray via:

permuteArrayLeft  pi arr == permuteArrayRight (inversePermutation pi) arr
permuteArrayRight pi arr == permuteArrayLeft  (inversePermutation pi) arr

permuteArrayRight :: IArray arr b => Permutation -> arr Int b -> arr Int b

The right (standard) action of permutations on sets.

permuteArrayRight pi2 (permuteArrayRight pi1 set) == permuteArrayRight (pi1 `multiplyPermutation` pi2) set

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

permuteListLeft :: forall a. Permutation -> [a] -> [a]

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

permuteListLeft perm set == permuteList (inversePermutation perm) set
fromPermutation (inversePermutation perm) == permuteListLeft perm [1..n]

permuteListRight :: forall a. Permutation -> [a] -> [a]

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

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

Sorting

sortingPermutationAsc :: Ord a => [a] -> Permutation

Given a list of things, we return a permutation which sorts them into ascending order, that is:

permuteList (sortingPermutationAsc xs) xs == sort xs

Note: if the things are not unique, then the sorting permutations is not unique either; we just return one of them.

sortingPermutationDesc :: Ord a => [a] -> Permutation

Given a list of things, we return a permutation which sorts them into descending order, that is:

permuteList (sortingPermutationDesc xs) xs == reverse (sort xs)

Note: if the things are not unique, then the sorting permutations is not unique either; we just return one of them.

ASCII drawing

asciiPermutation :: Permutation -> ASCII

Synonym for twoLineNotation

asciiDisjointCycles :: DisjointCycles -> ASCII

twoLineNotation :: Permutation -> ASCII

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.

inverseTwoLineNotation :: Permutation -> ASCII

The inverse two-line notation, where the it's the bottom line which is in standard order. The columns of this are a permutation of the columns twoLineNotation.

Remark: the top row of inverseTwoLineNotation perm is the same as the bottom row of twoLineNotation (inversePermutation perm).

genericTwoLineNotation :: [(Int, Int)] -> ASCII

Two-line notation for any set of numbers

List of permutations

permutations :: Int -> [Permutation]

A synonym for permutationsNaive

_permutations :: Int -> [[Int]]

permutationsNaive :: Int -> [Permutation]

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

_permutationsNaive :: Int -> [[Int]]

countPermutations :: Int -> Integer

# = n!

Random permutations

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

A synonym for randomPermutationDurstenfeld.

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

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

A synonym for randomCyclicPermutationSattolo.

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

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

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)

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

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

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

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

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

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