Safe Haskell | None |
---|---|
Language | Haskell98 |
Math.Algebra.Group.PermutationGroup
Description
A module for doing arithmetic in permutation groups.
Group elements are represented as permutations of underlying sets, and are entered and displayed
using a Haskell-friendly version of cycle notation. For example, the permutation (1 2 3)(4 5)
would be entered as p [[1,2,3],[4,5]]
, and displayed as [[1,2,3],[4,5]]. Permutations can be defined
over arbitrary underlying sets (types), not just the integers.
If g
and h
are group elements, then the expressions g*h
and g^-1
calculate product and inverse respectively.
- rotateL :: [a] -> [a]
- newtype Permutation a = P (Map a a)
- p :: Ord a => [[a]] -> Permutation a
- fromPairs :: Ord a => [(a, a)] -> Permutation a
- fromPairs' :: Ord a => [(a, a)] -> Permutation a
- toPairs :: Permutation a -> [(a, a)]
- fromList :: Ord a => [a] -> Permutation a
- supp :: Permutation a -> [a]
- (.^) :: Ord a => a -> Permutation a -> a
- (-^) :: Ord a => [a] -> Permutation a -> [a]
- fromCycles :: Ord a => [[a]] -> Permutation a
- toCycles :: Ord a => Permutation a -> [[a]]
- cycleOf :: Ord a => Permutation a -> a -> [a]
- parity :: Ord a => Permutation a -> Int
- sign :: (Ord a1, Num a) => Permutation a1 -> a
- orderElt :: Ord a => Permutation a -> Int
- (~^) :: (Ord a, Show a) => Permutation a -> Permutation a -> Permutation a
- comm :: (HasInverses a, Num a) => a -> a -> a
- closureS :: Ord a => [a] -> [a -> a] -> Set a
- closure :: Ord a => [a] -> [a -> a] -> [a]
- orbit :: Ord a => (a -> t -> a) -> a -> [t] -> [a]
- (.^^) :: Ord a => a -> [Permutation a] -> [a]
- orbitP :: Ord a => [Permutation a] -> a -> [a]
- orbitV :: Ord a => [Permutation a] -> a -> [a]
- (-^^) :: Ord a => [a] -> [Permutation a] -> [[a]]
- orbitB :: Ord a => [Permutation a] -> [a] -> [[a]]
- orbitE :: Ord a => [Permutation a] -> [a] -> [[a]]
- action :: Ord a => [a] -> (a -> a) -> Permutation a
- orbits :: Ord a => [Permutation a] -> [[a]]
- _C :: Integral a => a -> [Permutation a]
- _D :: Integral a => a -> [Permutation a]
- _D2 :: Integral a => a -> [Permutation a]
- _S :: Integral a => a -> [Permutation a]
- _A :: Integral a => a -> [Permutation a]
- dp :: (Ord a, Ord b) => [Permutation a] -> [Permutation b] -> [Permutation (Either a b)]
- wr :: (Ord t1, Ord t) => [Permutation t] -> [Permutation t1] -> [Permutation (t, t1)]
- toSn :: (Ord a, Ord k, Num a, Enum a) => [Permutation k] -> [Permutation a]
- fromDigits :: (Ord a, Num a) => Permutation [a] -> Permutation a
- fromDigits' :: Num a => [a] -> a
- fromBinary :: (Ord a, Num a) => Permutation [a] -> Permutation a
- fromBinary' :: Num a => [a] -> a
- elts :: (Num a, Ord a) => [a] -> [a]
- eltsS :: (Ord a, Num a) => [a] -> Set a
- order :: (Num a, Ord a) => [a] -> Int
- isMember :: (Ord a, Num a) => [a] -> a -> Bool
- minsupp :: Permutation c -> c
- orderTGS :: (Show a, Ord a, Num a1) => [Permutation a] -> a1
- eltsTGS :: (Show a, Ord a) => [Permutation a] -> [Permutation a]
- tgsFromSgs :: (Show a, Ord a) => [Permutation a] -> [Permutation a]
- orderSGS :: Ord a => [Permutation a] -> Integer
- gens :: (Ord a, Num a) => [a] -> [a]
- (~^^) :: (Show a, Ord a) => Permutation a -> [Permutation a] -> [Permutation a]
- conjClass :: (Show a, Ord a) => [Permutation a] -> Permutation a -> [Permutation a]
- conjClassReps :: (Ord a, Show a) => [Permutation a] -> [(Permutation a, Int)]
- reduceGens :: (Ord a, Num a) => [a] -> [a]
- isSubgp :: (Ord a, Num a) => [a] -> [a] -> Bool
- subgps :: (Ord a, Show a) => [Permutation a] -> [[Permutation a]]
- isMinimal :: (Show a, Ord a) => Permutation a -> Bool
- centralizer :: (Ord t, Num t) => [t] -> [t] -> [t]
- centre :: (Ord t, Num t) => [t] -> [t]
- normalizer :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [Permutation a]
- stabilizer :: (Show a, Ord a) => [Permutation a] -> a -> [Permutation a]
- ptStab :: (Show a, Ord a) => [Permutation a] -> [a] -> [Permutation a]
- setStab :: (Show a, Ord a) => [Permutation a] -> [a] -> [Permutation a]
- normalClosure :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [Permutation a]
- commutatorGp :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [Permutation a]
- derivedSubgp :: (Show a, Ord a) => [Permutation a] -> [Permutation a]
- (-*-) :: (Ord b, Num b) => [b] -> [b] -> [b]
- (-*) :: (Ord a, Num a) => [a] -> a -> [a]
- (*-) :: (Ord a, Num a) => a -> [a] -> [a]
- isNormal :: (Ord a, Show a) => [Permutation a] -> [Permutation a] -> Bool
- normalSubgps :: (Ord a, Show a) => [Permutation a] -> [[Permutation a]]
- isSimple :: (Show a, Ord a) => [Permutation a] -> Bool
- cosets :: (Ord t, Num t) => [t] -> [t] -> [[t]]
- quotientGp :: (Ord a, Show a) => [Permutation a] -> [Permutation a] -> [Permutation Int]
- (//) :: (Ord a, Show a) => [Permutation a] -> [Permutation a] -> [Permutation Int]
- (~~^) :: (Show a, Ord a) => [Permutation a] -> Permutation a -> [Permutation a]
- conjugateSubgps :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [[Permutation a]]
- subgpAction :: (Show a, Ord a1, Ord a, Num a1, Enum a1) => [Permutation a] -> [Permutation a] -> [Permutation a1]
- rrpr :: (Ord a, Num a) => [a] -> a -> Permutation a
- rrpr' :: (Ord a, Num a) => [a] -> a -> Permutation a
- permutationMatrix :: (Ord a, Num t) => [a] -> Permutation a -> [[t]]
Documentation
newtype Permutation a Source
A type for permutations, considered as functions or actions which can be performed on an underlying set.
Instances
(Eq k, Num k) => HopfAlgebra k (Permutation Int) | |
(Eq k, Num k) => Bialgebra k (Permutation Int) | |
(Eq k, Num k) => Coalgebra k (Permutation Int) | |
(Eq k, Num k) => Algebra k (Permutation Int) | |
(Eq k, Num k) => Module k (Permutation Int) Int | |
(Eq k, Num k) => Module k (Permutation Int) [Int] | |
Eq a => Eq (Permutation a) | |
(Ord a, Show a) => Num (Permutation a) | The Num instance is what enables us to write |
Ord a => Ord (Permutation a) | |
(Ord a, Show a) => Show (Permutation a) | |
(Ord a, Show a) => HasInverses (Permutation a) | The HasInverses instance is what enables us to write |
HasInverses (GroupAlgebra Q) | Note that the inverse of a group algebra element can only be efficiently calculated if the group generated by the non-zero terms is very small (eg <100 elements). |
p :: Ord a => [[a]] -> Permutation a Source
Construct a permutation from a list of cycles.
For example, p [[1,2,3],[4,5]]
returns the permutation that sends 1 to 2, 2 to 3, 3 to 1, 4 to 5, 5 to 4.
fromPairs :: Ord a => [(a, a)] -> Permutation a Source
fromPairs' :: Ord a => [(a, a)] -> Permutation a Source
toPairs :: Permutation a -> [(a, a)] Source
fromList :: Ord a => [a] -> Permutation a Source
supp :: Permutation a -> [a] Source
(.^) :: Ord a => a -> Permutation a -> a Source
x .^ g returns the image of a vertex or point x under the action of the permutation g.
For example, 1 .^ p [[1,2,3]]
returns 2.
The dot is meant to be a mnemonic for point or vertex.
(-^) :: Ord a => [a] -> Permutation a -> [a] Source
b -^ g returns the image of an edge or block b under the action of the permutation g.
For example, [1,2] -^ p [[1,4],[2,3]]
returns [3,4].
The dash is meant to be a mnemonic for edge or line or block.
fromCycles :: Ord a => [[a]] -> Permutation a Source
toCycles :: Ord a => Permutation a -> [[a]] Source
cycleOf :: Ord a => Permutation a -> a -> [a] Source
parity :: Ord a => Permutation a -> Int Source
sign :: (Ord a1, Num a) => Permutation a1 -> a Source
orderElt :: Ord a => Permutation a -> Int Source
(~^) :: (Ord a, Show a) => Permutation a -> Permutation a -> Permutation a infix 8 Source
g ~^ h returns the conjugate of g by h, that is, h^-1*g*h. The tilde is meant to a mnemonic, because conjugacy is an equivalence relation.
comm :: (HasInverses a, Num a) => a -> a -> a Source
(.^^) :: Ord a => a -> [Permutation a] -> [a] Source
x .^^ gs returns the orbit of the point or vertex x under the action of the gs
orbitP :: Ord a => [Permutation a] -> a -> [a] Source
orbitV :: Ord a => [Permutation a] -> a -> [a] Source
(-^^) :: Ord a => [a] -> [Permutation a] -> [[a]] Source
b -^^ gs returns the orbit of the block or edge b under the action of the gs
orbitB :: Ord a => [Permutation a] -> [a] -> [[a]] Source
orbitE :: Ord a => [Permutation a] -> [a] -> [[a]] Source
action :: Ord a => [a] -> (a -> a) -> Permutation a Source
orbits :: Ord a => [Permutation a] -> [[a]] Source
_C :: Integral a => a -> [Permutation a] Source
_C n returns generators for Cn, the cyclic group of order n
_D :: Integral a => a -> [Permutation a] Source
_D2 :: Integral a => a -> [Permutation a] Source
_S :: Integral a => a -> [Permutation a] Source
_S n returns generators for Sn, the symmetric group on [1..n]
_A :: Integral a => a -> [Permutation a] Source
_A n returns generators for An, the alternating group on [1..n]
dp :: (Ord a, Ord b) => [Permutation a] -> [Permutation b] -> [Permutation (Either a b)] Source
Given generators for groups H and K, acting on sets A and B respectively, return generators for the direct product H*K, acting on the disjoint union A+B (= Either A B)
wr :: (Ord t1, Ord t) => [Permutation t] -> [Permutation t1] -> [Permutation (t, t1)] Source
toSn :: (Ord a, Ord k, Num a, Enum a) => [Permutation k] -> [Permutation a] Source
fromDigits :: (Ord a, Num a) => Permutation [a] -> Permutation a Source
fromDigits' :: Num a => [a] -> a Source
fromBinary :: (Ord a, Num a) => Permutation [a] -> Permutation a Source
fromBinary' :: Num a => [a] -> a Source
elts :: (Num a, Ord a) => [a] -> [a] Source
Given generators for a group, return a (sorted) list of all elements of the group. Implemented using a naive closure algorithm, so only suitable for small groups (|G| < 10000)
order :: (Num a, Ord a) => [a] -> Int Source
Given generators for a group, return the order of the group (the number of elements). Implemented using a naive closure algorithm, so only suitable for small groups (|G| < 10000)
minsupp :: Permutation c -> c Source
eltsTGS :: (Show a, Ord a) => [Permutation a] -> [Permutation a] Source
tgsFromSgs :: (Show a, Ord a) => [Permutation a] -> [Permutation a] Source
orderSGS :: Ord a => [Permutation a] -> Integer Source
Given a strong generating set, return the order of the group it generates
(~^^) :: (Show a, Ord a) => Permutation a -> [Permutation a] -> [Permutation a] Source
conjClass :: (Show a, Ord a) => [Permutation a] -> Permutation a -> [Permutation a] Source
conjClassReps :: (Ord a, Show a) => [Permutation a] -> [(Permutation a, Int)] Source
conjClassReps gs returns conjugacy class representatives and sizes for the group generated by gs. This implementation is only suitable for use with small groups (|G| < 10000).
reduceGens :: (Ord a, Num a) => [a] -> [a] Source
subgps :: (Ord a, Show a) => [Permutation a] -> [[Permutation a]] Source
Return the subgroups of a group. Only suitable for use on small groups (eg < 100 elts)
centralizer :: (Ord t, Num t) => [t] -> [t] -> [t] Source
normalizer :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [Permutation a] Source
stabilizer :: (Show a, Ord a) => [Permutation a] -> a -> [Permutation a] Source
ptStab :: (Show a, Ord a) => [Permutation a] -> [a] -> [Permutation a] Source
setStab :: (Show a, Ord a) => [Permutation a] -> [a] -> [Permutation a] Source
normalClosure :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [Permutation a] Source
commutatorGp :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [Permutation a] Source
derivedSubgp :: (Show a, Ord a) => [Permutation a] -> [Permutation a] Source
isNormal :: (Ord a, Show a) => [Permutation a] -> [Permutation a] -> Bool Source
isNormal gs ks returns True if <ks> is normal in <gs>. Note, it is caller's responsibility to ensure that <ks> is a subgroup of <gs> (ie that each k is in <gs>).
normalSubgps :: (Ord a, Show a) => [Permutation a] -> [[Permutation a]] Source
Return the normal subgroups of a group. Only suitable for use on small groups (eg < 100 elts)
quotientGp :: (Ord a, Show a) => [Permutation a] -> [Permutation a] -> [Permutation Int] Source
quotientGp gs ks returns <gs> / <ks>
(//) :: (Ord a, Show a) => [Permutation a] -> [Permutation a] -> [Permutation Int] Source
Synonym for quotientGp
(~~^) :: (Show a, Ord a) => [Permutation a] -> Permutation a -> [Permutation a] Source
conjugateSubgps :: (Show a, Ord a) => [Permutation a] -> [Permutation a] -> [[Permutation a]] Source
subgpAction :: (Show a, Ord a1, Ord a, Num a1, Enum a1) => [Permutation a] -> [Permutation a] -> [Permutation a1] Source
rrpr :: (Ord a, Num a) => [a] -> a -> Permutation a Source
rrpr' :: (Ord a, Num a) => [a] -> a -> Permutation a Source
permutationMatrix :: (Ord a, Num t) => [a] -> Permutation a -> [[t]] Source