hmt-0.15: Haskell Music Theory

Safe Haskell | None
Language | Haskell98

Music.Theory.Permutations

Description

Permutation functions.

Synopsis

- factorial :: (Ord a, Num a) => a -> a
- nk_permutations :: Integral a => a -> a -> a
- n_permutations :: Integral a => a -> a
- permutation :: Eq a => [a] -> [a] -> Permute
- apply_permutation :: Eq a => Permute -> [a] -> [a]
- apply_permutation_c :: Eq a => [[Int]] -> [a] -> [a]
- non_invertible :: Permute -> Bool
- from_cycles :: [[Int]] -> Permute
- permutations_n :: Int -> [Permute]
- compose :: Permute -> Permute -> Permute
- two_line :: Permute -> ([Int], [Int])
- one_line :: Permute -> [Int]
- one_line_compact :: Permute -> String
- multiplication_table :: Int -> [[Permute]]

# Documentation

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

Factorial function.

    (factorial 13,maxBound::Int)

nk_permutations :: Integral a => a -> a -> a Source #

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

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

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]

non_invertible :: Permute -> Bool Source #

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

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

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

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

one_line_compact :: Permute -> String Source #

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