Math.Combinat.Permutations

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

Types

data Permutation

Standard notation for permutations. Internally it is an array of the integers [1..n].

Instances

Eq Permutation

Ord Permutation

Read Permutation

Show Permutation

data DisjointCycles

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

Instances

Eq DisjointCycles

Ord DisjointCycles

Read DisjointCycles

Show DisjointCycles

fromPermutation :: Permutation -> [Int]

permutationArray :: Permutation -> Array Int Int

toPermutationUnsafe :: [Int] -> Permutation

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

isPermutation :: [Int] -> Bool

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

toPermutation :: [Int] -> Permutation

Checks the input.

permutationSize :: Permutation -> Int

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

Disjoint cycles

fromDisjointCycles :: DisjointCycles -> [[Int]]

disjointCyclesUnsafe :: [[Int]] -> DisjointCycles

permutationToDisjointCycles :: Permutation -> DisjointCycles

This is compatible with Maple's convert(perm,'disjcyc').

disjointCyclesToPermutation :: Int -> DisjointCycles -> Permutation

isEvenPermutation :: Permutation -> Bool

isOddPermutation :: Permutation -> Bool

signOfPermutation :: Num a => Permutation -> a

Plus 1 or minus 1.

isCyclicPermutation :: Permutation -> Bool

Permutation groups

permute :: Permutation -> Array Int a -> Array Int a

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 left (as opposed to Knuth, where they act on the right). Thus,

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

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

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

The list should be of length n.

multiply :: Permutation -> Permutation -> Permutation

Multiplies two permutations together. See permute for our conventions.

inverse :: Permutation -> Permutation

The inverse permutation

Simple permutations

permutations :: Int -> [Permutation]

A synonym for permutationsNaive

_permutations :: Int -> [[Int]]

permutationsNaive :: Int -> [Permutation]

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.