| 1 | =head1 Name | ||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||
| 3 | Math::Groups - Find automorphisms of groups and isomorphisms between groups. | ||||||||||||||||||||||||||||
| 4 | |||||||||||||||||||||||||||||
| 5 | =head1 Synopsis | ||||||||||||||||||||||||||||
| 6 | |||||||||||||||||||||||||||||
| 7 | use Math::Groups; | ||||||||||||||||||||||||||||
| 8 | use Data::Dump qw(dump); | ||||||||||||||||||||||||||||
| 9 | use Math::Cartesian::Product; | ||||||||||||||||||||||||||||
| 10 | |||||||||||||||||||||||||||||
| 11 | # Print a cyclic group of order 4 | ||||||||||||||||||||||||||||
| 12 | |||||||||||||||||||||||||||||
| 13 | print dump(Group{($_[0]*$_[1]) % 5} 1..4)."\n"; | ||||||||||||||||||||||||||||
| 14 | |||||||||||||||||||||||||||||
| 15 | # elements => { | ||||||||||||||||||||||||||||
| 16 | # 1 => { 1 => 1, 2 => 2, 3 => 3, 4 => 4 }, | ||||||||||||||||||||||||||||
| 17 | # 2 => { 1 => 2, 2 => 4, 3 => 1, 4 => 3 }, | ||||||||||||||||||||||||||||
| 18 | # 3 => { 1 => 3, 2 => 1, 3 => 4, 4 => 2 }, | ||||||||||||||||||||||||||||
| 19 | # 4 => { 1 => 4, 2 => 3, 3 => 2, 4 => 1 }, | ||||||||||||||||||||||||||||
| 20 | # }, | ||||||||||||||||||||||||||||
| 21 | # identity => 1, | ||||||||||||||||||||||||||||
| 22 | # inverses => { 1 => 1, 2 => 3, 3 => 2, 4 => 4 }, | ||||||||||||||||||||||||||||
| 23 | # orders => { 1 => 0, 2 => 4, 3 => 4, 4 => 2 }, | ||||||||||||||||||||||||||||
| 24 | |||||||||||||||||||||||||||||
| 25 | |||||||||||||||||||||||||||||
| 26 | # Find the automorphisms of the cyclic group of order 4 | ||||||||||||||||||||||||||||
| 27 | |||||||||||||||||||||||||||||
| 28 | autoMorphisms {print dump({@_})."\n"} | ||||||||||||||||||||||||||||
| 29 | Group{($_[0]+$_[1]) % 4} 0..3; | ||||||||||||||||||||||||||||
| 30 | |||||||||||||||||||||||||||||
| 31 | # { 1 => 1, 2 => 2, 3 => 3 } | ||||||||||||||||||||||||||||
| 32 | # { 1 => 3, 2 => 2, 3 => 1 } | ||||||||||||||||||||||||||||
| 33 | |||||||||||||||||||||||||||||
| 34 | # Find the automorphisms of dihedral group of order 4 | ||||||||||||||||||||||||||||
| 35 | |||||||||||||||||||||||||||||
| 36 | my $corners = [cartesian {1} ([1,-1]) x 2]; | ||||||||||||||||||||||||||||
| 37 | my $cornerNumbers; | ||||||||||||||||||||||||||||
| 38 | map {my ($a, $b) = @{$$corners[$_]}; | ||||||||||||||||||||||||||||
| 39 | $cornerNumbers->{$a}{$b} = $_ | ||||||||||||||||||||||||||||
| 40 | } 0..$#$corners; | ||||||||||||||||||||||||||||
| 41 | |||||||||||||||||||||||||||||
| 42 | autoMorphisms {print dump({@_})."\n"} | ||||||||||||||||||||||||||||
| 43 | Group | ||||||||||||||||||||||||||||
| 44 | {my ($a, $b, $c, $d) = map {@$_} @$corners[@_]; | ||||||||||||||||||||||||||||
| 45 | $cornerNumbers->{$a*$c}{$b*$d} | ||||||||||||||||||||||||||||
| 46 | } 0..$#$corners; | ||||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | # { 1 => 1, 2 => 2, 3 => 3 } | ||||||||||||||||||||||||||||
| 49 | # { 1 => 1, 2 => 3, 3 => 2 } | ||||||||||||||||||||||||||||
| 50 | # { 1 => 2, 2 => 1, 3 => 3 } | ||||||||||||||||||||||||||||
| 51 | # { 1 => 3, 2 => 1, 3 => 2 } | ||||||||||||||||||||||||||||
| 52 | # { 1 => 2, 2 => 3, 3 => 1 } | ||||||||||||||||||||||||||||
| 53 | # { 1 => 3, 2 => 2, 3 => 1 } | ||||||||||||||||||||||||||||
| 54 | =cut | ||||||||||||||||||||||||||||
| 55 | |||||||||||||||||||||||||||||
| 56 | package Math::Groups; | ||||||||||||||||||||||||||||
| 57 | |||||||||||||||||||||||||||||
| 58 | #------------------------------------------------------------------------------- | ||||||||||||||||||||||||||||
| 59 | # Mathematical Groups | ||||||||||||||||||||||||||||
| 60 | # Philip R Brenan at gmail dot com, Appa Apps Ltd Inc, 2015 | ||||||||||||||||||||||||||||
| 61 | #------------------------------------------------------------------------------- | ||||||||||||||||||||||||||||
| 62 | |||||||||||||||||||||||||||||
| 63 | 1 | ▶ | use v5.18; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 64 | 1 | ▶ | use warnings FATAL => qw(all); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 65 | 1 | ▶ | use Carp; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 66 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 67 | 1 | ▶ | use utf8; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 68 | 1 | ▶ | use Math::Cartesian::Product; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 69 | 1 | ▶ | use Math::Permute::List; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 70 | 1 | ▶ | use Data::Dump qw(dump); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 71 | |||||||||||||||||||||||||||||
| 72 | 360 | ▶ | sub Elements {qw(elements)} # Constants | ||||||||||||||||||||||||||
|
Subroutine
Elements: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 73 | 170 | ▶ | sub Identity {qw(identity)} | ||||||||||||||||||||||||||
|
Subroutine
Identity: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 74 | 39 | ▶ | sub Inverses {qw(inverses)} | ||||||||||||||||||||||||||
|
Subroutine
Inverses: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 75 | 38 | ▶ | sub Orders {qw(orders)} | ||||||||||||||||||||||||||
|
Subroutine
Orders: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 76 | |||||||||||||||||||||||||||||
| 77 | 204 | ▶ | sub 𝗲($) {$_[0]->{&Elements}} # Multiplication table | ||||||||||||||||||||||||||
|
Subroutine
𝗲: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 78 | 159 | ▶ | sub e($) {$_[0]->{&Identity}} # Identity | ||||||||||||||||||||||||||
|
Subroutine
e: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 79 | 24 | ▶ | sub i($) {$_[0]->{&Inverses}} # Inverses | ||||||||||||||||||||||||||
|
Subroutine
i: called CC=1 SCAR=0.0
Pod
undocumented
| |||||||||||||||||||||||||||||
| 80 | |||||||||||||||||||||||||||||
| 81 | sub o($$$;$$) # Add one or two products to the group or retrieve a prior product | ||||||||||||||||||||||||||||
| 82 | 0 | ▶ | {my ($g, $a, $b, $c, $𝗰) = @_; # Group, first element $a, second element $b, $a*$b, $b*$a | ||||||||||||||||||||||||||
|
Subroutine
o: not called CC=6 SCAR=37.4
Pod
undocumented
| |||||||||||||||||||||||||||||
| 83 | 0 | my $𝗲 = 𝗲($g); # Elements | |||||||||||||||||||||||||||
| 84 | 0 | ▶ | if (@_ == 3) # Retrieve a prior product | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 85 | 0 | {return $𝗲->{$a}{$b}; | |||||||||||||||||||||||||||
| 86 | } | ||||||||||||||||||||||||||||
| 87 | 0 | ▶ | if (@_ == 4 or @_ == 5) # Add a product to the group for a*b | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition0%0/3
@_ == 4 or @_ == 5
MC/DC0%0/2
@_ == 4 or @_ == 5
@_ == 4
@_ == 5
Truth table0%0/3
A or B
A= @_ == 4B= @_ == 5
| |||||||||||||||||||||||||||||
| 88 | 0 | {$g->{&Identity} = $g->{&Inverses} = undef; # Destroy cached identity and inverses as we have modified the group | |||||||||||||||||||||||||||
| 89 | } | ||||||||||||||||||||||||||||
| 90 | 0 | ▶ | if (@_ == 4) # Add a product to the group for a*b | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 91 | 0 | {$𝗲->{$a}{$b} = $c; | |||||||||||||||||||||||||||
| 92 | 0 | return $g; # Return group to allow for chaining if desired | |||||||||||||||||||||||||||
| 93 | } | ||||||||||||||||||||||||||||
| 94 | 0 | ▶ | if (@_ == 5) # Add products to the group for a*b and b*a | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 95 | 0 | {$𝗲->{$a}{$b} = $c; | |||||||||||||||||||||||||||
| 96 | 0 | $𝗲->{$b}{$a} = $𝗰; | |||||||||||||||||||||||||||
| 97 | 0 | return $g; # Return group to allow for chaining if desired | |||||||||||||||||||||||||||
| 98 | } | ||||||||||||||||||||||||||||
| 99 | 0 | confess "Wrong number of parameters, should be 3 to get a prior product or 4 for single put or 5 for double put!"; | |||||||||||||||||||||||||||
| 100 | } | ||||||||||||||||||||||||||||
| 101 | |||||||||||||||||||||||||||||
| 102 | sub identity($) # Find the identity element - assumes that the group has been checked for uniqueness and closure | ||||||||||||||||||||||||||||
| 103 | 15 | ▶ | {my ($g) = @_; # Group | ||||||||||||||||||||||||||
|
Subroutine
identity: called CC=7 SCAR=19.5
Pod
documented
| |||||||||||||||||||||||||||||
| 104 | 15 | my $e = e($g); # Identity from cache | |||||||||||||||||||||||||||
| 105 | 15 | ▶ | return $e if $e; # Check cache | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 106 | 11 | my $𝗲 = 𝗲($g); # Elements | |||||||||||||||||||||||||||
| 107 | 11 | for my $a(keys %$𝗲) # Find the identity and confirm that there is only one | |||||||||||||||||||||||||||
| 108 | 26 | {my $n = 0; # Number of elements for which $a is an identity | |||||||||||||||||||||||||||
| 109 | 26 | for my $b(keys %$𝗲) | |||||||||||||||||||||||||||
| 110 | 59 | ▶ | {last unless $𝗲->{$a}{$b} eq $b and $𝗲->{$b}{$a} eq $b; # Check whether it could be an indentity | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$𝗲->{$a}{$b} eq $b and $𝗲->{$b}{$a} eq $b
MC/DC50%1/2
$𝗲->{$a}{$b} eq $b and $𝗲->{$b}{$a} eq $b
$𝗲->{$a}{$b} eq $b
$𝗲->{$b}{$a} eq $b
Truth table66%2/3
A and B
A= $𝗲->{$a}{$b} eq $bB= $𝗲->{$b}{$a} eq $b
| |||||||||||||||||||||||||||||
| 111 | 44 | $n++ # Possible identity | |||||||||||||||||||||||||||
| 112 | } | ||||||||||||||||||||||||||||
| 113 | 26 | ▶ | return $g->{&Identity} = $a if $n == keys %$𝗲 # Save identity in cache | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 114 | } | ||||||||||||||||||||||||||||
| 115 | 0 | confess "No identity found!"; | |||||||||||||||||||||||||||
| 116 | } | ||||||||||||||||||||||||||||
| 117 | |||||||||||||||||||||||||||||
| 118 | sub inverse($$) # Find the inverse of an element - assumes that identity has been dound | ||||||||||||||||||||||||||||
| 119 | 24 | ▶ | {my ($g, $a) = @_; # Group, element for which an inverse is required | ||||||||||||||||||||||||||
|
Subroutine
inverse: called CC=7 SCAR=19.8
Pod
documented
| |||||||||||||||||||||||||||||
| 120 | 24 | my $𝗲 = 𝗲($g); # Elements | |||||||||||||||||||||||||||
| 121 | 24 | my $i = i($g); # Inverses | |||||||||||||||||||||||||||
| 122 | 24 | ▶ | confess "Not a group element: $a" unless defined $𝗲->{$a}; # Validate element | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 123 | 24 | ▶ | return $i->{$a} if defined($i) and defined($i->{$a}); # Return if inverse is in cache | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
defined $i and defined $i->{$a}
MC/DC50%1/2
defined $i and defined $i->{$a}
defined $i
defined $i->{$a}
Truth table66%2/3
A and B
A= defined $iB= defined $i->{$a}
| |||||||||||||||||||||||||||||
| 124 | 12 | my $e = identity($g); # Find identity | |||||||||||||||||||||||||||
| 125 | 12 | for my $b(keys %$𝗲) # Each element | |||||||||||||||||||||||||||
| 126 | 30 | {my ($p, $q) = ($𝗲->{$a}{$b}, $𝗲->{$b}{$a}); # Product each way | |||||||||||||||||||||||||||
| 127 | 30 | ▶ | if ($p eq $e and $q eq $e) # Inverse if both products equal identity | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
$p eq $e and $q eq $e
MC/DC50%1/2
$p eq $e and $q eq $e
$p eq $e
$q eq $e
Truth table66%2/3
A and B
A= $p eq $eB= $q eq $e
| |||||||||||||||||||||||||||||
| 128 | 12 | {$g->{&Inverses}->{$a} = $b; # Cache inverse | |||||||||||||||||||||||||||
| 129 | 12 | return $b # Inverse | |||||||||||||||||||||||||||
| 130 | } | ||||||||||||||||||||||||||||
| 131 | } | ||||||||||||||||||||||||||||
| 132 | 0 | confess "No inverse found for $a" | |||||||||||||||||||||||||||
| 133 | } | ||||||||||||||||||||||||||||
| 134 | |||||||||||||||||||||||||||||
| 135 | sub orders($) # Order of each element | ||||||||||||||||||||||||||||
| 136 | 3 | ▶ | {my ($g) = @_; | ||||||||||||||||||||||||||
|
Subroutine
orders: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||
| 137 | 3 | my $e = e($g); # Identity | |||||||||||||||||||||||||||
| 138 | 3 | my $𝗲 = 𝗲($g); # Elements | |||||||||||||||||||||||||||
| 139 | 3 | for my $A(keys %$𝗲) # Each element | |||||||||||||||||||||||||||
| 140 | 12 | {my $a = $A; | |||||||||||||||||||||||||||
| 141 | 12 | my $o = 1; | |||||||||||||||||||||||||||
| 142 | 12 | for(1..keys %$𝗲) # Multiply until we reach the identity | |||||||||||||||||||||||||||
| 143 | 29 | ▶ | {last if $a eq $e; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 144 | 17 | $a = $𝗲->{$a}{$A}; | |||||||||||||||||||||||||||
| 145 | 17 | ++$o; | |||||||||||||||||||||||||||
| 146 | } | ||||||||||||||||||||||||||||
| 147 | 12 | $g->{&Orders}{$A} = $o; # Save order | |||||||||||||||||||||||||||
| 148 | } | ||||||||||||||||||||||||||||
| 149 | 3 | $g->{&Orders}{$e} = 0; # Correct order of identity | |||||||||||||||||||||||||||
| 150 | } | ||||||||||||||||||||||||||||
| 151 | |||||||||||||||||||||||||||||
| 152 | sub order($;$) # Order of an element | ||||||||||||||||||||||||||||
| 153 | 28 | ▶ | {my ($g, $a) = @_; | ||||||||||||||||||||||||||
|
Subroutine
order: called CC=2 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 154 | 28 | my $𝗲 = 𝗲($g); | |||||||||||||||||||||||||||
| 155 | 28 | ▶ | return scalar keys %$𝗲 if @_ == 1; # Order of group | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 156 | 12 | $g->{&Orders}{$a}; # Order of element | |||||||||||||||||||||||||||
| 157 | } | ||||||||||||||||||||||||||||
| 158 | |||||||||||||||||||||||||||||
| 159 | sub elements($) # Elements in group | ||||||||||||||||||||||||||||
| 160 | 0 | ▶ | {my ($g) = @_; | ||||||||||||||||||||||||||
|
Subroutine
elements: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||||||||||||||||||||
| 161 | 0 | my $𝗲 = 𝗲($g); | |||||||||||||||||||||||||||
| 162 | 0 | sort keys %$𝗲 | |||||||||||||||||||||||||||
| 163 | } | ||||||||||||||||||||||||||||
| 164 | |||||||||||||||||||||||||||||
| 165 | sub check($) # Check that it really is a group | ||||||||||||||||||||||||||||
| 166 | 3 | ▶ | {my ($g) = @_; | ||||||||||||||||||||||||||
|
Subroutine
check: called CC=11 SCAR=25.7
Pod
undocumented
| |||||||||||||||||||||||||||||
| 167 | 3 | my $𝗲 = 𝗲($g); # Elements | |||||||||||||||||||||||||||
| 168 | 3 | for my $a(keys %$𝗲) # Check each operation | |||||||||||||||||||||||||||
| 169 | 12 | {my %row; my %col; # Check each element is unique in each row and in each column | |||||||||||||||||||||||||||
| 170 | 12 | for my $b(keys %$𝗲) | |||||||||||||||||||||||||||
| 171 | 48 | {my ($c, $𝗰) = ($𝗲->{$a}{$b}, $𝗲->{$b}{$a}); # Result of operation each way | |||||||||||||||||||||||||||
| 172 | 48 | ▶ | confess "Missing product for $a * $b" unless defined $c; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 173 | 48 | ▶ | confess "Missing product for $b * $a" unless defined $𝗰; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 174 | 48 | ▶ | confess "Group not closed for $c == $a * $b" unless defined $𝗲->{$c}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 175 | 48 | ▶ | confess "Group not closed for $𝗰 == $b * $a" unless defined $𝗲->{$𝗰}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 176 | 48 | ▶ | if (defined(my $p = $row{$c})) # Check each product in a row is unique | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 177 | 0 | {confess "Duplicate product $c == $a * $b and $a * $p"; # Helpfully provided duplicated product | |||||||||||||||||||||||||||
| 178 | } | ||||||||||||||||||||||||||||
| 179 | 48 | $row{$c} = $b; # Record product as already present in this row | |||||||||||||||||||||||||||
| 180 | 48 | ▶ | if (defined(my $p = $col{$𝗰})) # Check each product in a column is unique | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 181 | 0 | {confess "Duplicate product $𝗰 == $b * $a and $b * $p"; # Helpfully provided duplicated product | |||||||||||||||||||||||||||
| 182 | } | ||||||||||||||||||||||||||||
| 183 | 48 | $row{$c} = $b; # Record product as already present in this column | |||||||||||||||||||||||||||
| 184 | } | ||||||||||||||||||||||||||||
| 185 | } | ||||||||||||||||||||||||||||
| 186 | 3 | identity($g); # Check that the group has an identity | |||||||||||||||||||||||||||
| 187 | 3 | for my $a(keys %$𝗲) # Find the identity and confirm that there is only one | |||||||||||||||||||||||||||
| 188 | 12 | ▶ | {confess "No inverse for: $a" unless defined inverse($g, $a); # Helpfully indicate element with no inverse | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 189 | } | ||||||||||||||||||||||||||||
| 190 | 3 | orders($g); # Order if each element | |||||||||||||||||||||||||||
| 191 | 3 | 1 # It is a group | |||||||||||||||||||||||||||
| 192 | } | ||||||||||||||||||||||||||||
| 193 | |||||||||||||||||||||||||||||
| 194 | sub Group(&@) # Create a group | ||||||||||||||||||||||||||||
| 195 | 3 | ▶ | {my $sub = shift; # Operator, elements | ||||||||||||||||||||||||||
|
Subroutine
Group: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||
| 196 | 3 | my $g = bless {&Elements=>{}, &Inverses=>{}, &Orders=>{}}; # Empty group | |||||||||||||||||||||||||||
| 197 | 3 | for my $a(@_) # Create multiplication table | |||||||||||||||||||||||||||
| 198 | 12 | {for my $b(@_) | |||||||||||||||||||||||||||
| 199 | 48 | {$g->{&Elements}{$a}{$b} = &$sub($a, $b); | |||||||||||||||||||||||||||
| 200 | } | ||||||||||||||||||||||||||||
| 201 | } | ||||||||||||||||||||||||||||
| 202 | 3 | check($g); # Check we have a group | |||||||||||||||||||||||||||
| 203 | 3 | $g # Return results | |||||||||||||||||||||||||||
| 204 | } | ||||||||||||||||||||||||||||
| 205 | |||||||||||||||||||||||||||||
| 206 | sub abelian($) # Abelian? | ||||||||||||||||||||||||||||
| 207 | 3 | ▶ | {my ($g) = @_; # Group | ||||||||||||||||||||||||||
|
Subroutine
abelian: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||
| 208 | 3 | my $𝗲 = 𝗲($g); # Elements | |||||||||||||||||||||||||||
| 209 | 3 | for my $a(keys %$𝗲) # Check each operation | |||||||||||||||||||||||||||
| 210 | 12 | {for my $b(keys %$𝗲) | |||||||||||||||||||||||||||
| 211 | 48 | ▶ | {return 0 unless $g->{&Elements}{$a}{$b} == $g->{&Elements}{$b}{$a}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 212 | } | ||||||||||||||||||||||||||||
| 213 | } | ||||||||||||||||||||||||||||
| 214 | 1 # Abelian | ||||||||||||||||||||||||||||
| 215 | 3 | } | |||||||||||||||||||||||||||
| 216 | |||||||||||||||||||||||||||||
| 217 | sub cyclic($) # Cyclic - return a generating element or undef if no such element | ||||||||||||||||||||||||||||
| 218 | 3 | ▶ | {my ($g) = @_; # Group | ||||||||||||||||||||||||||
|
Subroutine
cyclic: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||
| 219 | 3 | my $N = order($g); | |||||||||||||||||||||||||||
| 220 | 3 | ▶ | while(my ($e, $o) = each %{$g->{&Orders}}) # Order of each element | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 221 | 7 | ▶ | {return $e if $o && $o == $N; # Return generating element | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$o and $o == $N
MC/DC100%2/2
$o and $o == $N
$o
$o == $N
Truth table100%3/3
A and B
A= $oB= $o == $N
| |||||||||||||||||||||||||||||
| 222 | } | ||||||||||||||||||||||||||||
| 223 | undef # Not cyclic | ||||||||||||||||||||||||||||
| 224 | 1 | } | |||||||||||||||||||||||||||
| 225 | |||||||||||||||||||||||||||||
| 226 | sub subGroup($@) # Sub group | ||||||||||||||||||||||||||||
| 227 | 9 | ▶ | {my $g = shift; # Group followed by sub group elements excluding identity | ||||||||||||||||||||||||||
|
Subroutine
subGroup: called CC=4 SCAR=13.9
Pod
documented
| |||||||||||||||||||||||||||||
| 228 | 9 | my %g = map {$_=>1} @_, $g->e; # Add identity as that is always present in a sub group | |||||||||||||||||||||||||||
| 229 | 9 | for my $a(@_) # Check each product | |||||||||||||||||||||||||||
| 230 | 9 | {for my $b(@_) | |||||||||||||||||||||||||||
| 231 | 9 | ▶ | {return 0 unless $g{$g->{&Elements}{$a}{$b}}; # Not a sub group unless product is within sub group | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 232 | } | ||||||||||||||||||||||||||||
| 233 | } | ||||||||||||||||||||||||||||
| 234 | 1 # Sub group | ||||||||||||||||||||||||||||
| 235 | 5 | } | |||||||||||||||||||||||||||
| 236 | |||||||||||||||||||||||||||||
| 237 | sub homoMorphic($$@) # Homomorphism between two groups | ||||||||||||||||||||||||||||
| 238 | 61 | ▶ | {my $g = shift; # First group | ||||||||||||||||||||||||||
|
Subroutine
homoMorphic: called CC=8 SCAR=20.9
Pod
documented
| |||||||||||||||||||||||||||||
| 239 | 61 | my $𝗴 = shift; # Second group | |||||||||||||||||||||||||||
| 240 | 61 | ▶ | ref($𝗴) eq __PACKAGE__ or confess "Second parameter must be a group too!"; # Check it is a group isomorphism | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 241 | 61 | my %m = @_; # Mapping between groups | |||||||||||||||||||||||||||
| 242 | 61 | $m{e($g)} = e($𝗴); # Include identity to identity in mapping | |||||||||||||||||||||||||||
| 243 | 61 | my $e = 𝗲($g); # Elements in first group | |||||||||||||||||||||||||||
| 244 | 61 | my $𝗲 = 𝗲($𝗴); # Elements in second group | |||||||||||||||||||||||||||
| 245 | 61 | ▶ | while(my ($a, $b) = each %m) # Check elements come from the correct groups | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 246 | 244 | ▶ | {confess "Not a group element of first group: $a" unless $e->{$a}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 247 | 244 | ▶ | confess "Not a group element of second group: $b" unless $𝗲->{$b}; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 248 | } | ||||||||||||||||||||||||||||
| 249 | 61 | for my $a(keys %m) # Check each product | |||||||||||||||||||||||||||
| 250 | 198 | {for my $b(keys %m) | |||||||||||||||||||||||||||
| 251 | 746 | ▶ | {return 0 unless $m{$e->{$a}{$b}} eq $𝗲->{$m{$a}}{$m{$b}}; # Apply | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 252 | } | ||||||||||||||||||||||||||||
| 253 | } | ||||||||||||||||||||||||||||
| 254 | 1 # Homomorphic | ||||||||||||||||||||||||||||
| 255 | 43 | } | |||||||||||||||||||||||||||
| 256 | |||||||||||||||||||||||||||||
| 257 | sub isoMorphic($$@) # Isomorphic | ||||||||||||||||||||||||||||
| 258 | 39 | ▶ | {my $g = shift; # First group | ||||||||||||||||||||||||||
|
Subroutine
isoMorphic: called CC=4 SCAR=14.0
Pod
documented
| |||||||||||||||||||||||||||||
| 259 | 39 | my $𝗴 = shift; # Second group | |||||||||||||||||||||||||||
| 260 | 39 | ▶ | ref($𝗴) eq __PACKAGE__ or confess "Second parameter must be a group too!"; # Check it is a group isomorphism | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 261 | 39 | my %m = @_; # Mapping between groups | |||||||||||||||||||||||||||
| 262 | 39 | my %𝗺 = reverse %m; # Mapping between groups | |||||||||||||||||||||||||||
| 263 | 39 | ▶ | keys(%m) == keys(%𝗺) or confess "Please supply a bijective mapping!"; # Check that the mapping is bijective | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 264 | 39 | ▶ | $g->homoMorphic($𝗴, %m) && $𝗴->homoMorphic($g, %𝗺) # Bijective homomorphism is an isomorphism | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 265 | } | ||||||||||||||||||||||||||||
| 266 | |||||||||||||||||||||||||||||
| 267 | sub isoMorphisms(&$$) # Find all the isomorphisms between two groups | ||||||||||||||||||||||||||||
| 268 | 5 | ▶ | {my ($sub, $g, $𝗴) = @_; # Sub to call to process found isomorphisms, first group, second group | ||||||||||||||||||||||||||
|
Subroutine
isoMorphisms: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||
| 269 | 5 | ▶ | ref($𝗴) eq __PACKAGE__ or confess "Second parameter must be a group too!"; # Check it is a group | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 270 | 5 | ▶ | order($g) == order($𝗴) or confess "Groups have different orders!"; # Check groups have same order | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 271 | 5 | my $i = e($g); # Identity of first group | |||||||||||||||||||||||||||
| 272 | 5 | my $𝗶 = e($𝗴); # Identity of second group | |||||||||||||||||||||||||||
| 273 | 5 | my $e = [grep {$_ ne $i} sort keys %{𝗲($g)}]; # Elements of first group in fixed order without identity | |||||||||||||||||||||||||||
| 274 | 5 | my $𝗲 = [grep {$_ ne $𝗶} sort keys %{𝗲($𝗴)}]; # Elements of second group in fixed order without identity | |||||||||||||||||||||||||||
| 275 | permute # Permute the elements to obtain all possible mappings | ||||||||||||||||||||||||||||
| 276 | 30 | ▶ | {my %m = map {$$e[$_]=>$$𝗲[$_[$_]]} 0..$#_; # Mapping to test | ||||||||||||||||||||||||||
|
Subroutine
__ANON__: called CC=2 SCAR=6.9
| |||||||||||||||||||||||||||||
| 277 | 30 | ▶ | &$sub(%m) if isoMorphic($g, $𝗴, %m); # Process mapping if isomorphic | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 278 | 5 | } 0..$#$e; # Elements to permute | |||||||||||||||||||||||||||
| 279 | } | ||||||||||||||||||||||||||||
| 280 | |||||||||||||||||||||||||||||
| 281 | sub autoMorphic($@) # Automorphic | ||||||||||||||||||||||||||||
| 282 | 5 | ▶ | {my $g = shift; # Group | ||||||||||||||||||||||||||
|
Subroutine
autoMorphic: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 283 | 5 | $g->isoMorphic($g, @_) # Check | |||||||||||||||||||||||||||
| 284 | } | ||||||||||||||||||||||||||||
| 285 | |||||||||||||||||||||||||||||
| 286 | sub autoMorphisms(&$) # Find all the automorphisms of a group | ||||||||||||||||||||||||||||
| 287 | 3 | ▶ | {my ($sub, $g) = @_; # Sub to call to process found automorphisms, group | ||||||||||||||||||||||||||
|
Subroutine
autoMorphisms: called CC=1 SCAR=0.0
Pod
documented
| |||||||||||||||||||||||||||||
| 288 | 3 | &isoMorphisms($sub,$g,$g) | |||||||||||||||||||||||||||
| 289 | } | ||||||||||||||||||||||||||||
| 290 | |||||||||||||||||||||||||||||
| 291 | # Export details | ||||||||||||||||||||||||||||
| 292 | |||||||||||||||||||||||||||||
| 293 | 1 | require 5; | |||||||||||||||||||||||||||
| 294 | 1 | require Exporter; | |||||||||||||||||||||||||||
| 295 | |||||||||||||||||||||||||||||
| 296 | 1 | ▶ | use vars qw(@ISA @EXPORT $VERSION); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 297 | |||||||||||||||||||||||||||||
| 298 | 1 | @ISA = qw(Exporter); | |||||||||||||||||||||||||||
| 299 | 1 | @EXPORT = qw(Group autoMorphisms isoMorphisms); | |||||||||||||||||||||||||||
| 300 | |||||||||||||||||||||||||||||
| 301 | 1 | our $VERSION = '1.002'; # Sunday 23 Aug 2015 | |||||||||||||||||||||||||||
| 302 | |||||||||||||||||||||||||||||
| 303 | =head1 Description | ||||||||||||||||||||||||||||
| 304 | |||||||||||||||||||||||||||||
| 305 | Find automorphisms of groups and isomorphisms between groups. | ||||||||||||||||||||||||||||
| 306 | |||||||||||||||||||||||||||||
| 307 | A group automorphism is a bijection on the set of elements of a group which | ||||||||||||||||||||||||||||
| 308 | preserves the group product. | ||||||||||||||||||||||||||||
| 309 | |||||||||||||||||||||||||||||
| 310 | A group isomorphism is a bijection between the sets of elements of two groups | ||||||||||||||||||||||||||||
| 311 | which preserves the group product. | ||||||||||||||||||||||||||||
| 312 | |||||||||||||||||||||||||||||
| 313 | =head2 identity(group) | ||||||||||||||||||||||||||||
| 314 | |||||||||||||||||||||||||||||
| 315 | Returns the identity element. | ||||||||||||||||||||||||||||
| 316 | |||||||||||||||||||||||||||||
| 317 | =head2 inverse(group, element) | ||||||||||||||||||||||||||||
| 318 | |||||||||||||||||||||||||||||
| 319 | Returns the inverse of an element. | ||||||||||||||||||||||||||||
| 320 | |||||||||||||||||||||||||||||
| 321 | =head2 orders(group) | ||||||||||||||||||||||||||||
| 322 | |||||||||||||||||||||||||||||
| 323 | Returns a hash which supplies the order of each element. The identity is | ||||||||||||||||||||||||||||
| 324 | assigned an order of zero. | ||||||||||||||||||||||||||||
| 325 | |||||||||||||||||||||||||||||
| 326 | =head2 order(group, element) | ||||||||||||||||||||||||||||
| 327 | |||||||||||||||||||||||||||||
| 328 | Returns the order of an element with the group. | ||||||||||||||||||||||||||||
| 329 | |||||||||||||||||||||||||||||
| 330 | =head2 elements(group) | ||||||||||||||||||||||||||||
| 331 | |||||||||||||||||||||||||||||
| 332 | Returns a hash whose keys are the elements if the group. The value at each key | ||||||||||||||||||||||||||||
| 333 | of this hash is another hash which gives the product in this group. | ||||||||||||||||||||||||||||
| 334 | |||||||||||||||||||||||||||||
| 335 | =head2 Group sub elements... | ||||||||||||||||||||||||||||
| 336 | |||||||||||||||||||||||||||||
| 337 | Creates a group with the specified elements as multiplied by C<sub>. The first | ||||||||||||||||||||||||||||
| 338 | parameter is a subroutine that forms the product of each pair of elements drawn | ||||||||||||||||||||||||||||
| 339 | from the following list of elements. | ||||||||||||||||||||||||||||
| 340 | |||||||||||||||||||||||||||||
| 341 | =head2 abelian(group) | ||||||||||||||||||||||||||||
| 342 | |||||||||||||||||||||||||||||
| 343 | Returns 1 if the group is Abelian, else 0. | ||||||||||||||||||||||||||||
| 344 | |||||||||||||||||||||||||||||
| 345 | =head2 cyclic(group) | ||||||||||||||||||||||||||||
| 346 | |||||||||||||||||||||||||||||
| 347 | If the group is cyclic, returns an element that generates the group, else | ||||||||||||||||||||||||||||
| 348 | undef. | ||||||||||||||||||||||||||||
| 349 | |||||||||||||||||||||||||||||
| 350 | =head2 subGroup(groups, elements...) | ||||||||||||||||||||||||||||
| 351 | |||||||||||||||||||||||||||||
| 352 | Returns 1 if the elements specified plus the identity element form a sub group | ||||||||||||||||||||||||||||
| 353 | of the group else 0. | ||||||||||||||||||||||||||||
| 354 | |||||||||||||||||||||||||||||
| 355 | =head2 homoMorphic(group1, group2, mapping...) | ||||||||||||||||||||||||||||
| 356 | |||||||||||||||||||||||||||||
| 357 | Returns 1 if mapping forms a homomorphism from group 1 to group 2, else 0. | ||||||||||||||||||||||||||||
| 358 | |||||||||||||||||||||||||||||
| 359 | The mapping is a subset of the Cartesian product of the elements of | ||||||||||||||||||||||||||||
| 360 | group 1 and the elements of group 2 flattened into a list. The pair: | ||||||||||||||||||||||||||||
| 361 | |||||||||||||||||||||||||||||
| 362 | (identity of group 1, identity of group 2) | ||||||||||||||||||||||||||||
| 363 | |||||||||||||||||||||||||||||
| 364 | is added for you so there is no need to specify it unless you wish to. | ||||||||||||||||||||||||||||
| 365 | |||||||||||||||||||||||||||||
| 366 | =head2 isoMorphic(group1, group2, mapping...) | ||||||||||||||||||||||||||||
| 367 | |||||||||||||||||||||||||||||
| 368 | Returns 1 if the mapping is an isomorphism from group 1 to group 2, else 0. | ||||||||||||||||||||||||||||
| 369 | |||||||||||||||||||||||||||||
| 370 | The mapping is a subset of the Cartesian product of the elements of | ||||||||||||||||||||||||||||
| 371 | group 1 and the elements of group 2 flattened into a list. The pair: | ||||||||||||||||||||||||||||
| 372 | |||||||||||||||||||||||||||||
| 373 | (identity of group 1, identity of group 2) | ||||||||||||||||||||||||||||
| 374 | |||||||||||||||||||||||||||||
| 375 | is added for you so there is no need to specify it unless you wish to. | ||||||||||||||||||||||||||||
| 376 | |||||||||||||||||||||||||||||
| 377 | =head2 isoMorphisms sub group1, group 2 | ||||||||||||||||||||||||||||
| 378 | |||||||||||||||||||||||||||||
| 379 | Finds all the isomorphisms between two groups and calls C<sub> to process each | ||||||||||||||||||||||||||||
| 380 | of them as they are discovered. | ||||||||||||||||||||||||||||
| 381 | |||||||||||||||||||||||||||||
| 382 | The parameter list to sub is a pair for each element of group 1 indicating the | ||||||||||||||||||||||||||||
| 383 | corresponding element of group 2 under the isomorphism. | ||||||||||||||||||||||||||||
| 384 | |||||||||||||||||||||||||||||
| 385 | =head2 autoMorphic(group, mapping) | ||||||||||||||||||||||||||||
| 386 | |||||||||||||||||||||||||||||
| 387 | Returns 1 if the mapping is an automorphism from the group to itself, else 0. | ||||||||||||||||||||||||||||
| 388 | |||||||||||||||||||||||||||||
| 389 | The mapping is a subset of the Cartesian product of the elements of | ||||||||||||||||||||||||||||
| 390 | the group squared flattened into a list. The pair: | ||||||||||||||||||||||||||||
| 391 | |||||||||||||||||||||||||||||
| 392 | (identity of group, identity of group) | ||||||||||||||||||||||||||||
| 393 | |||||||||||||||||||||||||||||
| 394 | is added for you so there is no need to specify it unless you wish to. | ||||||||||||||||||||||||||||
| 395 | |||||||||||||||||||||||||||||
| 396 | =head2 autoMorphisms sub group | ||||||||||||||||||||||||||||
| 397 | |||||||||||||||||||||||||||||
| 398 | Finds all the automorphisms of the groups and calls C<sub> to process each | ||||||||||||||||||||||||||||
| 399 | of them as they are discovered. | ||||||||||||||||||||||||||||
| 400 | |||||||||||||||||||||||||||||
| 401 | The parameter list to sub is a pair for each element of the group indicating the | ||||||||||||||||||||||||||||
| 402 | corresponding element under the automorphism. | ||||||||||||||||||||||||||||
| 403 | |||||||||||||||||||||||||||||
| 404 | =head1 Export | ||||||||||||||||||||||||||||
| 405 | |||||||||||||||||||||||||||||
| 406 | The C<Group()>, C<isoMorphisms()>, C<autoMorphisms()> functions are exported. | ||||||||||||||||||||||||||||
| 407 | |||||||||||||||||||||||||||||
| 408 | =head1 Installation | ||||||||||||||||||||||||||||
| 409 | |||||||||||||||||||||||||||||
| 410 | Standard Module::Build process for building and installing modules: | ||||||||||||||||||||||||||||
| 411 | |||||||||||||||||||||||||||||
| 412 | perl Build.PL | ||||||||||||||||||||||||||||
| 413 | ./Build | ||||||||||||||||||||||||||||
| 414 | ./Build test | ||||||||||||||||||||||||||||
| 415 | ./Build install | ||||||||||||||||||||||||||||
| 416 | |||||||||||||||||||||||||||||
| 417 | Or, if you're on a platform (like DOS or Windows) that doesn't require | ||||||||||||||||||||||||||||
| 418 | the "./" notation, you can do this: | ||||||||||||||||||||||||||||
| 419 | |||||||||||||||||||||||||||||
| 420 | perl Build.PL | ||||||||||||||||||||||||||||
| 421 | Build | ||||||||||||||||||||||||||||
| 422 | Build test | ||||||||||||||||||||||||||||
| 423 | Build install | ||||||||||||||||||||||||||||
| 424 | |||||||||||||||||||||||||||||
| 425 | =head1 Author | ||||||||||||||||||||||||||||
| 426 | |||||||||||||||||||||||||||||
| 427 | Philip R Brenan at gmail dot com | ||||||||||||||||||||||||||||
| 428 | |||||||||||||||||||||||||||||
| 429 | http://www.appaapps.com | ||||||||||||||||||||||||||||
| 430 | |||||||||||||||||||||||||||||
| 431 | =head1 See Also | ||||||||||||||||||||||||||||
| 432 | |||||||||||||||||||||||||||||
| 433 | =over | ||||||||||||||||||||||||||||
| 434 | |||||||||||||||||||||||||||||
| 435 | =item L<Math::Cartesian::Product> | ||||||||||||||||||||||||||||
| 436 | |||||||||||||||||||||||||||||
| 437 | =item L<Math::Permute::List> | ||||||||||||||||||||||||||||
| 438 | |||||||||||||||||||||||||||||
| 439 | =back | ||||||||||||||||||||||||||||
| 440 | |||||||||||||||||||||||||||||
| 441 | =head1 Copyright | ||||||||||||||||||||||||||||
| 442 | |||||||||||||||||||||||||||||
| 443 | This module is free software. It may be used, redistributed and/or | ||||||||||||||||||||||||||||
| 444 | modified under the same terms as Perl itself. | ||||||||||||||||||||||||||||
| 445 | |||||||||||||||||||||||||||||
| 446 | =cut | ||||||||||||||||||||||||||||