/
perm_groups.py
5381 lines (4458 loc) · 178 KB
/
perm_groups.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
from math import log
from itertools import chain, islice, product
from sympy.combinatorics import Permutation
from sympy.combinatorics.permutations import (_af_commutes_with, _af_invert,
_af_rmul, _af_rmuln, _af_pow, Cycle)
from sympy.combinatorics.util import (_check_cycles_alt_sym,
_distribute_gens_by_base, _orbits_transversals_from_bsgs,
_handle_precomputed_bsgs, _base_ordering, _strong_gens_from_distr,
_strip, _strip_af)
from sympy.core import Basic
from sympy.core.random import _randrange, randrange, choice
from sympy.core.symbol import Symbol
from sympy.core.sympify import _sympify
from sympy.functions.combinatorial.factorials import factorial
from sympy.ntheory import primefactors, sieve
from sympy.ntheory.factor_ import (factorint, multiplicity)
from sympy.ntheory.primetest import isprime
from sympy.utilities.iterables import has_variety, is_sequence, uniq
rmul = Permutation.rmul_with_af
_af_new = Permutation._af_new
class PermutationGroup(Basic):
r"""The class defining a Permutation group.
Explanation
===========
``PermutationGroup([p1, p2, ..., pn])`` returns the permutation group
generated by the list of permutations. This group can be supplied
to Polyhedron if one desires to decorate the elements to which the
indices of the permutation refer.
Examples
========
>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> from sympy.combinatorics import Polyhedron
The permutations corresponding to motion of the front, right and
bottom face of a $2 \times 2$ Rubik's cube are defined:
>>> F = Permutation(2, 19, 21, 8)(3, 17, 20, 10)(4, 6, 7, 5)
>>> R = Permutation(1, 5, 21, 14)(3, 7, 23, 12)(8, 10, 11, 9)
>>> D = Permutation(6, 18, 14, 10)(7, 19, 15, 11)(20, 22, 23, 21)
These are passed as permutations to PermutationGroup:
>>> G = PermutationGroup(F, R, D)
>>> G.order()
3674160
The group can be supplied to a Polyhedron in order to track the
objects being moved. An example involving the $2 \times 2$ Rubik's cube is
given there, but here is a simple demonstration:
>>> a = Permutation(2, 1)
>>> b = Permutation(1, 0)
>>> G = PermutationGroup(a, b)
>>> P = Polyhedron(list('ABC'), pgroup=G)
>>> P.corners
(A, B, C)
>>> P.rotate(0) # apply permutation 0
>>> P.corners
(A, C, B)
>>> P.reset()
>>> P.corners
(A, B, C)
Or one can make a permutation as a product of selected permutations
and apply them to an iterable directly:
>>> P10 = G.make_perm([0, 1])
>>> P10('ABC')
['C', 'A', 'B']
See Also
========
sympy.combinatorics.polyhedron.Polyhedron,
sympy.combinatorics.permutations.Permutation
References
==========
.. [1] Holt, D., Eick, B., O'Brien, E.
"Handbook of Computational Group Theory"
.. [2] Seress, A.
"Permutation Group Algorithms"
.. [3] https://en.wikipedia.org/wiki/Schreier_vector
.. [4] https://en.wikipedia.org/wiki/Nielsen_transformation#Product_replacement_algorithm
.. [5] Frank Celler, Charles R.Leedham-Green, Scott H.Murray,
Alice C.Niemeyer, and E.A.O'Brien. "Generating Random
Elements of a Finite Group"
.. [6] https://en.wikipedia.org/wiki/Block_%28permutation_group_theory%29
.. [7] http://www.algorithmist.com/index.php/Union_Find
.. [8] https://en.wikipedia.org/wiki/Multiply_transitive_group#Multiply_transitive_groups
.. [9] https://en.wikipedia.org/wiki/Center_%28group_theory%29
.. [10] https://en.wikipedia.org/wiki/Centralizer_and_normalizer
.. [11] http://groupprops.subwiki.org/wiki/Derived_subgroup
.. [12] https://en.wikipedia.org/wiki/Nilpotent_group
.. [13] http://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf
.. [14] https://www.gap-system.org/Manuals/doc/ref/manual.pdf
"""
is_group = True
def __new__(cls, *args, dups=True, **kwargs):
"""The default constructor. Accepts Cycle and Permutation forms.
Removes duplicates unless ``dups`` keyword is ``False``.
"""
if not args:
args = [Permutation()]
else:
args = list(args[0] if is_sequence(args[0]) else args)
if not args:
args = [Permutation()]
if any(isinstance(a, Cycle) for a in args):
args = [Permutation(a) for a in args]
if has_variety(a.size for a in args):
degree = kwargs.pop('degree', None)
if degree is None:
degree = max(a.size for a in args)
for i in range(len(args)):
if args[i].size != degree:
args[i] = Permutation(args[i], size=degree)
if dups:
args = list(uniq([_af_new(list(a)) for a in args]))
if len(args) > 1:
args = [g for g in args if not g.is_identity]
return Basic.__new__(cls, *args, **kwargs)
def __init__(self, *args, **kwargs):
self._generators = list(self.args)
self._order = None
self._center = []
self._is_abelian = None
self._is_transitive = None
self._is_sym = None
self._is_alt = None
self._is_primitive = None
self._is_nilpotent = None
self._is_solvable = None
self._is_trivial = None
self._transitivity_degree = None
self._max_div = None
self._is_perfect = None
self._is_cyclic = None
self._r = len(self._generators)
self._degree = self._generators[0].size
# these attributes are assigned after running schreier_sims
self._base = []
self._strong_gens = []
self._strong_gens_slp = []
self._basic_orbits = []
self._transversals = []
self._transversal_slp = []
# these attributes are assigned after running _random_pr_init
self._random_gens = []
# finite presentation of the group as an instance of `FpGroup`
self._fp_presentation = None
def __getitem__(self, i):
return self._generators[i]
def __contains__(self, i):
"""Return ``True`` if *i* is contained in PermutationGroup.
Examples
========
>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> p = Permutation(1, 2, 3)
>>> Permutation(3) in PermutationGroup(p)
True
"""
if not isinstance(i, Permutation):
raise TypeError("A PermutationGroup contains only Permutations as "
"elements, not elements of type %s" % type(i))
return self.contains(i)
def __len__(self):
return len(self._generators)
def equals(self, other):
"""Return ``True`` if PermutationGroup generated by elements in the
group are same i.e they represent the same PermutationGroup.
Examples
========
>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> p = Permutation(0, 1, 2, 3, 4, 5)
>>> G = PermutationGroup([p, p**2])
>>> H = PermutationGroup([p**2, p])
>>> G.generators == H.generators
False
>>> G.equals(H)
True
"""
if not isinstance(other, PermutationGroup):
return False
set_self_gens = set(self.generators)
set_other_gens = set(other.generators)
# before reaching the general case there are also certain
# optimisation and obvious cases requiring less or no actual
# computation.
if set_self_gens == set_other_gens:
return True
# in the most general case it will check that each generator of
# one group belongs to the other PermutationGroup and vice-versa
for gen1 in set_self_gens:
if not other.contains(gen1):
return False
for gen2 in set_other_gens:
if not self.contains(gen2):
return False
return True
def __mul__(self, other):
"""
Return the direct product of two permutation groups as a permutation
group.
Explanation
===========
This implementation realizes the direct product by shifting the index
set for the generators of the second group: so if we have ``G`` acting
on ``n1`` points and ``H`` acting on ``n2`` points, ``G*H`` acts on
``n1 + n2`` points.
Examples
========
>>> from sympy.combinatorics.named_groups import CyclicGroup
>>> G = CyclicGroup(5)
>>> H = G*G
>>> H
PermutationGroup([
(9)(0 1 2 3 4),
(5 6 7 8 9)])
>>> H.order()
25
"""
if isinstance(other, Permutation):
return Coset(other, self, dir='+')
gens1 = [perm._array_form for perm in self.generators]
gens2 = [perm._array_form for perm in other.generators]
n1 = self._degree
n2 = other._degree
start = list(range(n1))
end = list(range(n1, n1 + n2))
for i in range(len(gens2)):
gens2[i] = [x + n1 for x in gens2[i]]
gens2 = [start + gen for gen in gens2]
gens1 = [gen + end for gen in gens1]
together = gens1 + gens2
gens = [_af_new(x) for x in together]
return PermutationGroup(gens)
def _random_pr_init(self, r, n, _random_prec_n=None):
r"""Initialize random generators for the product replacement algorithm.
Explanation
===========
The implementation uses a modification of the original product
replacement algorithm due to Leedham-Green, as described in [1],
pp. 69-71; also, see [2], pp. 27-29 for a detailed theoretical
analysis of the original product replacement algorithm, and [4].
The product replacement algorithm is used for producing random,
uniformly distributed elements of a group `G` with a set of generators
`S`. For the initialization ``_random_pr_init``, a list ``R`` of
`\max\{r, |S|\}` group generators is created as the attribute
``G._random_gens``, repeating elements of `S` if necessary, and the
identity element of `G` is appended to ``R`` - we shall refer to this
last element as the accumulator. Then the function ``random_pr()``
is called ``n`` times, randomizing the list ``R`` while preserving
the generation of `G` by ``R``. The function ``random_pr()`` itself
takes two random elements ``g, h`` among all elements of ``R`` but
the accumulator and replaces ``g`` with a randomly chosen element
from `\{gh, g(~h), hg, (~h)g\}`. Then the accumulator is multiplied
by whatever ``g`` was replaced by. The new value of the accumulator is
then returned by ``random_pr()``.
The elements returned will eventually (for ``n`` large enough) become
uniformly distributed across `G` ([5]). For practical purposes however,
the values ``n = 50, r = 11`` are suggested in [1].
Notes
=====
THIS FUNCTION HAS SIDE EFFECTS: it changes the attribute
self._random_gens
See Also
========
random_pr
"""
deg = self.degree
random_gens = [x._array_form for x in self.generators]
k = len(random_gens)
if k < r:
for i in range(k, r):
random_gens.append(random_gens[i - k])
acc = list(range(deg))
random_gens.append(acc)
self._random_gens = random_gens
# handle randomized input for testing purposes
if _random_prec_n is None:
for i in range(n):
self.random_pr()
else:
for i in range(n):
self.random_pr(_random_prec=_random_prec_n[i])
def _union_find_merge(self, first, second, ranks, parents, not_rep):
"""Merges two classes in a union-find data structure.
Explanation
===========
Used in the implementation of Atkinson's algorithm as suggested in [1],
pp. 83-87. The class merging process uses union by rank as an
optimization. ([7])
Notes
=====
THIS FUNCTION HAS SIDE EFFECTS: the list of class representatives,
``parents``, the list of class sizes, ``ranks``, and the list of
elements that are not representatives, ``not_rep``, are changed due to
class merging.
See Also
========
minimal_block, _union_find_rep
References
==========
.. [1] Holt, D., Eick, B., O'Brien, E.
"Handbook of computational group theory"
.. [7] http://www.algorithmist.com/index.php/Union_Find
"""
rep_first = self._union_find_rep(first, parents)
rep_second = self._union_find_rep(second, parents)
if rep_first != rep_second:
# union by rank
if ranks[rep_first] >= ranks[rep_second]:
new_1, new_2 = rep_first, rep_second
else:
new_1, new_2 = rep_second, rep_first
total_rank = ranks[new_1] + ranks[new_2]
if total_rank > self.max_div:
return -1
parents[new_2] = new_1
ranks[new_1] = total_rank
not_rep.append(new_2)
return 1
return 0
def _union_find_rep(self, num, parents):
"""Find representative of a class in a union-find data structure.
Explanation
===========
Used in the implementation of Atkinson's algorithm as suggested in [1],
pp. 83-87. After the representative of the class to which ``num``
belongs is found, path compression is performed as an optimization
([7]).
Notes
=====
THIS FUNCTION HAS SIDE EFFECTS: the list of class representatives,
``parents``, is altered due to path compression.
See Also
========
minimal_block, _union_find_merge
References
==========
.. [1] Holt, D., Eick, B., O'Brien, E.
"Handbook of computational group theory"
.. [7] http://www.algorithmist.com/index.php/Union_Find
"""
rep, parent = num, parents[num]
while parent != rep:
rep = parent
parent = parents[rep]
# path compression
temp, parent = num, parents[num]
while parent != rep:
parents[temp] = rep
temp = parent
parent = parents[temp]
return rep
@property
def base(self):
r"""Return a base from the Schreier-Sims algorithm.
Explanation
===========
For a permutation group `G`, a base is a sequence of points
`B = (b_1, b_2, \dots, b_k)` such that no element of `G` apart
from the identity fixes all the points in `B`. The concepts of
a base and strong generating set and their applications are
discussed in depth in [1], pp. 87-89 and [2], pp. 55-57.
An alternative way to think of `B` is that it gives the
indices of the stabilizer cosets that contain more than the
identity permutation.
Examples
========
>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> G = PermutationGroup([Permutation(0, 1, 3)(2, 4)])
>>> G.base
[0, 2]
See Also
========
strong_gens, basic_transversals, basic_orbits, basic_stabilizers
"""
if self._base == []:
self.schreier_sims()
return self._base
def baseswap(self, base, strong_gens, pos, randomized=False,
transversals=None, basic_orbits=None, strong_gens_distr=None):
r"""Swap two consecutive base points in base and strong generating set.
Explanation
===========
If a base for a group `G` is given by `(b_1, b_2, \dots, b_k)`, this
function returns a base `(b_1, b_2, \dots, b_{i+1}, b_i, \dots, b_k)`,
where `i` is given by ``pos``, and a strong generating set relative
to that base. The original base and strong generating set are not
modified.
The randomized version (default) is of Las Vegas type.
Parameters
==========
base, strong_gens
The base and strong generating set.
pos
The position at which swapping is performed.
randomized
A switch between randomized and deterministic version.
transversals
The transversals for the basic orbits, if known.
basic_orbits
The basic orbits, if known.
strong_gens_distr
The strong generators distributed by basic stabilizers, if known.
Returns
=======
(base, strong_gens)
``base`` is the new base, and ``strong_gens`` is a generating set
relative to it.
Examples
========
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> from sympy.combinatorics.testutil import _verify_bsgs
>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> S = SymmetricGroup(4)
>>> S.schreier_sims()
>>> S.base
[0, 1, 2]
>>> base, gens = S.baseswap(S.base, S.strong_gens, 1, randomized=False)
>>> base, gens
([0, 2, 1],
[(0 1 2 3), (3)(0 1), (1 3 2),
(2 3), (1 3)])
check that base, gens is a BSGS
>>> S1 = PermutationGroup(gens)
>>> _verify_bsgs(S1, base, gens)
True
See Also
========
schreier_sims
Notes
=====
The deterministic version of the algorithm is discussed in
[1], pp. 102-103; the randomized version is discussed in [1], p.103, and
[2], p.98. It is of Las Vegas type.
Notice that [1] contains a mistake in the pseudocode and
discussion of BASESWAP: on line 3 of the pseudocode,
`|\beta_{i+1}^{\left\langle T\right\rangle}|` should be replaced by
`|\beta_{i}^{\left\langle T\right\rangle}|`, and the same for the
discussion of the algorithm.
"""
# construct the basic orbits, generators for the stabilizer chain
# and transversal elements from whatever was provided
transversals, basic_orbits, strong_gens_distr = \
_handle_precomputed_bsgs(base, strong_gens, transversals,
basic_orbits, strong_gens_distr)
base_len = len(base)
degree = self.degree
# size of orbit of base[pos] under the stabilizer we seek to insert
# in the stabilizer chain at position pos + 1
size = len(basic_orbits[pos])*len(basic_orbits[pos + 1]) \
//len(_orbit(degree, strong_gens_distr[pos], base[pos + 1]))
# initialize the wanted stabilizer by a subgroup
if pos + 2 > base_len - 1:
T = []
else:
T = strong_gens_distr[pos + 2][:]
# randomized version
if randomized is True:
stab_pos = PermutationGroup(strong_gens_distr[pos])
schreier_vector = stab_pos.schreier_vector(base[pos + 1])
# add random elements of the stabilizer until they generate it
while len(_orbit(degree, T, base[pos])) != size:
new = stab_pos.random_stab(base[pos + 1],
schreier_vector=schreier_vector)
T.append(new)
# deterministic version
else:
Gamma = set(basic_orbits[pos])
Gamma.remove(base[pos])
if base[pos + 1] in Gamma:
Gamma.remove(base[pos + 1])
# add elements of the stabilizer until they generate it by
# ruling out member of the basic orbit of base[pos] along the way
while len(_orbit(degree, T, base[pos])) != size:
gamma = next(iter(Gamma))
x = transversals[pos][gamma]
temp = x._array_form.index(base[pos + 1]) # (~x)(base[pos + 1])
if temp not in basic_orbits[pos + 1]:
Gamma = Gamma - _orbit(degree, T, gamma)
else:
y = transversals[pos + 1][temp]
el = rmul(x, y)
if el(base[pos]) not in _orbit(degree, T, base[pos]):
T.append(el)
Gamma = Gamma - _orbit(degree, T, base[pos])
# build the new base and strong generating set
strong_gens_new_distr = strong_gens_distr[:]
strong_gens_new_distr[pos + 1] = T
base_new = base[:]
base_new[pos], base_new[pos + 1] = base_new[pos + 1], base_new[pos]
strong_gens_new = _strong_gens_from_distr(strong_gens_new_distr)
for gen in T:
if gen not in strong_gens_new:
strong_gens_new.append(gen)
return base_new, strong_gens_new
@property
def basic_orbits(self):
r"""
Return the basic orbits relative to a base and strong generating set.
Explanation
===========
If `(b_1, b_2, \dots, b_k)` is a base for a group `G`, and
`G^{(i)} = G_{b_1, b_2, \dots, b_{i-1}}` is the ``i``-th basic stabilizer
(so that `G^{(1)} = G`), the ``i``-th basic orbit relative to this base
is the orbit of `b_i` under `G^{(i)}`. See [1], pp. 87-89 for more
information.
Examples
========
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> S = SymmetricGroup(4)
>>> S.basic_orbits
[[0, 1, 2, 3], [1, 2, 3], [2, 3]]
See Also
========
base, strong_gens, basic_transversals, basic_stabilizers
"""
if self._basic_orbits == []:
self.schreier_sims()
return self._basic_orbits
@property
def basic_stabilizers(self):
r"""
Return a chain of stabilizers relative to a base and strong generating
set.
Explanation
===========
The ``i``-th basic stabilizer `G^{(i)}` relative to a base
`(b_1, b_2, \dots, b_k)` is `G_{b_1, b_2, \dots, b_{i-1}}`. For more
information, see [1], pp. 87-89.
Examples
========
>>> from sympy.combinatorics.named_groups import AlternatingGroup
>>> A = AlternatingGroup(4)
>>> A.schreier_sims()
>>> A.base
[0, 1]
>>> for g in A.basic_stabilizers:
... print(g)
...
PermutationGroup([
(3)(0 1 2),
(1 2 3)])
PermutationGroup([
(1 2 3)])
See Also
========
base, strong_gens, basic_orbits, basic_transversals
"""
if self._transversals == []:
self.schreier_sims()
strong_gens = self._strong_gens
base = self._base
if not base: # e.g. if self is trivial
return []
strong_gens_distr = _distribute_gens_by_base(base, strong_gens)
basic_stabilizers = []
for gens in strong_gens_distr:
basic_stabilizers.append(PermutationGroup(gens))
return basic_stabilizers
@property
def basic_transversals(self):
"""
Return basic transversals relative to a base and strong generating set.
Explanation
===========
The basic transversals are transversals of the basic orbits. They
are provided as a list of dictionaries, each dictionary having
keys - the elements of one of the basic orbits, and values - the
corresponding transversal elements. See [1], pp. 87-89 for more
information.
Examples
========
>>> from sympy.combinatorics.named_groups import AlternatingGroup
>>> A = AlternatingGroup(4)
>>> A.basic_transversals
[{0: (3), 1: (3)(0 1 2), 2: (3)(0 2 1), 3: (0 3 1)}, {1: (3), 2: (1 2 3), 3: (1 3 2)}]
See Also
========
strong_gens, base, basic_orbits, basic_stabilizers
"""
if self._transversals == []:
self.schreier_sims()
return self._transversals
def composition_series(self):
r"""
Return the composition series for a group as a list
of permutation groups.
Explanation
===========
The composition series for a group `G` is defined as a
subnormal series `G = H_0 > H_1 > H_2 \ldots` A composition
series is a subnormal series such that each factor group
`H(i+1) / H(i)` is simple.
A subnormal series is a composition series only if it is of
maximum length.
The algorithm works as follows:
Starting with the derived series the idea is to fill
the gap between `G = der[i]` and `H = der[i+1]` for each
`i` independently. Since, all subgroups of the abelian group
`G/H` are normal so, first step is to take the generators
`g` of `G` and add them to generators of `H` one by one.
The factor groups formed are not simple in general. Each
group is obtained from the previous one by adding one
generator `g`, if the previous group is denoted by `H`
then the next group `K` is generated by `g` and `H`.
The factor group `K/H` is cyclic and it's order is
`K.order()//G.order()`. The series is then extended between
`K` and `H` by groups generated by powers of `g` and `H`.
The series formed is then prepended to the already existing
series.
Examples
========
>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> from sympy.combinatorics.named_groups import CyclicGroup
>>> S = SymmetricGroup(12)
>>> G = S.sylow_subgroup(2)
>>> C = G.composition_series()
>>> [H.order() for H in C]
[1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1]
>>> G = S.sylow_subgroup(3)
>>> C = G.composition_series()
>>> [H.order() for H in C]
[243, 81, 27, 9, 3, 1]
>>> G = CyclicGroup(12)
>>> C = G.composition_series()
>>> [H.order() for H in C]
[12, 6, 3, 1]
"""
der = self.derived_series()
if not all(g.is_identity for g in der[-1].generators):
raise NotImplementedError('Group should be solvable')
series = []
for i in range(len(der)-1):
H = der[i+1]
up_seg = []
for g in der[i].generators:
K = PermutationGroup([g] + H.generators)
order = K.order() // H.order()
down_seg = []
for p, e in factorint(order).items():
for _ in range(e):
down_seg.append(PermutationGroup([g] + H.generators))
g = g**p
up_seg = down_seg + up_seg
H = K
up_seg[0] = der[i]
series.extend(up_seg)
series.append(der[-1])
return series
def coset_transversal(self, H):
"""Return a transversal of the right cosets of self by its subgroup H
using the second method described in [1], Subsection 4.6.7
"""
if not H.is_subgroup(self):
raise ValueError("The argument must be a subgroup")
if H.order() == 1:
return self._elements
self._schreier_sims(base=H.base) # make G.base an extension of H.base
base = self.base
base_ordering = _base_ordering(base, self.degree)
identity = Permutation(self.degree - 1)
transversals = self.basic_transversals[:]
# transversals is a list of dictionaries. Get rid of the keys
# so that it is a list of lists and sort each list in
# the increasing order of base[l]^x
for l, t in enumerate(transversals):
transversals[l] = sorted(t.values(),
key = lambda x: base_ordering[base[l]^x])
orbits = H.basic_orbits
h_stabs = H.basic_stabilizers
g_stabs = self.basic_stabilizers
indices = [x.order()//y.order() for x, y in zip(g_stabs, h_stabs)]
# T^(l) should be a right transversal of H^(l) in G^(l) for
# 1<=l<=len(base). While H^(l) is the trivial group, T^(l)
# contains all the elements of G^(l) so we might just as well
# start with l = len(h_stabs)-1
if len(g_stabs) > len(h_stabs):
T = g_stabs[len(h_stabs)]._elements
else:
T = [identity]
l = len(h_stabs)-1
t_len = len(T)
while l > -1:
T_next = []
for u in transversals[l]:
if u == identity:
continue
b = base_ordering[base[l]^u]
for t in T:
p = t*u
if all(base_ordering[h^p] >= b for h in orbits[l]):
T_next.append(p)
if t_len + len(T_next) == indices[l]:
break
if t_len + len(T_next) == indices[l]:
break
T += T_next
t_len += len(T_next)
l -= 1
T.remove(identity)
T = [identity] + T
return T
def _coset_representative(self, g, H):
"""Return the representative of Hg from the transversal that
would be computed by ``self.coset_transversal(H)``.
"""
if H.order() == 1:
return g
# The base of self must be an extension of H.base.
if not(self.base[:len(H.base)] == H.base):
self._schreier_sims(base=H.base)
orbits = H.basic_orbits[:]
h_transversals = [list(_.values()) for _ in H.basic_transversals]
transversals = [list(_.values()) for _ in self.basic_transversals]
base = self.base
base_ordering = _base_ordering(base, self.degree)
def step(l, x):
gamma = sorted(orbits[l], key = lambda y: base_ordering[y^x])[0]
i = [base[l]^h for h in h_transversals[l]].index(gamma)
x = h_transversals[l][i]*x
if l < len(orbits)-1:
for u in transversals[l]:
if base[l]^u == base[l]^x:
break
x = step(l+1, x*u**-1)*u
return x
return step(0, g)
def coset_table(self, H):
"""Return the standardised (right) coset table of self in H as
a list of lists.
"""
# Maybe this should be made to return an instance of CosetTable
# from fp_groups.py but the class would need to be changed first
# to be compatible with PermutationGroups
if not H.is_subgroup(self):
raise ValueError("The argument must be a subgroup")
T = self.coset_transversal(H)
n = len(T)
A = list(chain.from_iterable((gen, gen**-1)
for gen in self.generators))
table = []
for i in range(n):
row = [self._coset_representative(T[i]*x, H) for x in A]
row = [T.index(r) for r in row]
table.append(row)
# standardize (this is the same as the algorithm used in coset_table)
# If CosetTable is made compatible with PermutationGroups, this
# should be replaced by table.standardize()
A = range(len(A))
gamma = 1
for alpha, a in product(range(n), A):
beta = table[alpha][a]
if beta >= gamma:
if beta > gamma:
for x in A:
z = table[gamma][x]
table[gamma][x] = table[beta][x]
table[beta][x] = z
for i in range(n):
if table[i][x] == beta:
table[i][x] = gamma
elif table[i][x] == gamma:
table[i][x] = beta
gamma += 1
if gamma >= n-1:
return table
def center(self):
r"""
Return the center of a permutation group.
Explanation
===========
The center for a group `G` is defined as
`Z(G) = \{z\in G | \forall g\in G, zg = gz \}`,
the set of elements of `G` that commute with all elements of `G`.
It is equal to the centralizer of `G` inside `G`, and is naturally a
subgroup of `G` ([9]).
Examples
========
>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> D = DihedralGroup(4)
>>> G = D.center()
>>> G.order()
2
See Also
========
centralizer
Notes
=====
This is a naive implementation that is a straightforward application
of ``.centralizer()``
"""
return self.centralizer(self)
def centralizer(self, other):
r"""
Return the centralizer of a group/set/element.
Explanation
===========
The centralizer of a set of permutations ``S`` inside
a group ``G`` is the set of elements of ``G`` that commute with all
elements of ``S``::
`C_G(S) = \{ g \in G | gs = sg \forall s \in S\}` ([10])
Usually, ``S`` is a subset of ``G``, but if ``G`` is a proper subgroup of
the full symmetric group, we allow for ``S`` to have elements outside
``G``.
It is naturally a subgroup of ``G``; the centralizer of a permutation
group is equal to the centralizer of any set of generators for that
group, since any element commuting with the generators commutes with
any product of the generators.
Parameters
==========
other
a permutation group/list of permutations/single permutation
Examples
========
>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
... CyclicGroup)
>>> S = SymmetricGroup(6)
>>> C = CyclicGroup(6)