Music.Theory.Permutations

Permutation functions.

Documentation

factorial :: (Ord a, Num a) => a -> a

Factorial function.

 (factorial 13,maxBound::Int)

nk_permutations :: Integral a => a -> a -> a

Number of k element permutations of a set of n elements.

 (nk_permutations 4 3,nk_permutations 13 3) == (24,1716)

n_permutations :: Integral a => a -> a

Number of nk permutations where n == k.

 map n_permutations [1..8] == [1,2,6,24,120,720,5040,40320]
 n_permutations 16 `div` 1000000 == 20922789

permutation :: Eq a => [a] -> [a] -> Permute

Generate the permutation from p to q, ie. the permutation that, when applied to p, gives q.

 apply_permutation (permutation [0,1,3] [1,0,3]) [0,1,3] == [1,0,3]

apply_permutation :: Eq a => Permute -> [a] -> [a]

Apply permutation f to p.

 let p = permutation [1..4] [4,3,2,1]
 in apply_permutation p [1..4] == [4,3,2,1]

apply_permutation_c :: Eq a => [[Int]] -> [a] -> [a]

Composition of apply_permutation and from_cycles.

 apply_permutation_c [[0,3],[1,2]] [1..4] == [4,3,2,1]
 apply_permutation_c [[0,2],[1],[3,4]] [1..5] == [3,2,1,5,4]
 apply_permutation_c [[0,1,4],[2,3]] [1..5] == [2,5,4,3,1]
 apply_permutation_c [[0,1,3],[2,4]] [1..5] == [2,4,5,1,3]

non_invertible :: Permute -> Bool

True if the inverse of p is p.

 non_invertible (permutation [0,1,3] [1,0,3]) == True

 let p = permutation [1..4] [4,3,2,1]
 in non_invertible p == True && P.cycles p == [[0,3],[1,2]]

from_cycles :: [[Int]] -> Permute

Generate a permutation from the cycles c.

 apply_permutation (from_cycles [[0,1,2,3]]) [1..4] == [2,3,4,1]

permutations_n :: Int -> [Permute]

Generate all permutations of size n.

 map one_line (permutations_n 3) == [[1,2,3],[1,3,2]
                                    ,[2,1,3],[2,3,1]
                                    ,[3,1,2],[3,2,1]]

compose :: Permute -> Permute -> Permute

Composition of q then p.

 let {p = from_cycles [[0,2],[1],[3,4]]
     ;q = from_cycles [[0,1,4],[2,3]]
     ;r = p `compose` q}
 in apply_permutation r [1,2,3,4,5] == [2,4,5,1,3]

two_line :: Permute -> ([Int], [Int])

Two line notation of p.

 two_line (permutation [0,1,3] [1,0,3]) == ([1,2,3],[2,1,3])

one_line :: Permute -> [Int]

One line notation of p.

 one_line (permutation [0,1,3] [1,0,3]) == [2,1,3]

 map one_line (permutations_n 3) == [[1,2,3],[1,3,2]
                                    ,[2,1,3],[2,3,1]
                                    ,[3,1,2],[3,2,1]]

one_line_compact :: Permute -> String

Variant of one_line that produces a compact string.

 one_line_compact (permutation [0,1,3] [1,0,3]) == "213"

 let p = permutations_n 3
 in unwords (map one_line_compact p) == "123 132 213 231 312 321"

multiplication_table :: Int -> [[Permute]]

Multiplication table of symmetric group n.

 unlines (map (unwords . map one_line_compact) (multiplication_table 3))

 ==> 123 132 213 231 312 321
     132 123 312 321 213 231
     213 231 123 132 321 312
     231 213 321 312 123 132
     312 321 132 123 231 213
     321 312 231 213 132 123