Music.Theory.Permutations

Description

Permutation functions.

Synopsis

# Documentation

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

Factorial function.

``` (factorial 13,maxBound::Int)
```

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

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

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

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

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

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

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

Generate a permutation from the cycles c.

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

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

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

Two line notation of p.

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

one_line :: Permute -> [Int]Source

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

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

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