Safe Haskell | None |
---|---|
Language | Haskell98 |
Permutation functions.
- 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
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