ggSnddlmZddlmZddlmZddlmZGddeZGddeZ d S) isprime)PermutationGroup)DefaultPrinting) free_groupc*eZdZdZdZddZdZdZdS)PolycyclicGroupTNcn||_||_||_|st|j||n||_dS)a Parameters ========== pc_sequence : list A sequence of elements whose classes generate the cyclic factor groups of pc_series. pc_series : list A subnormal sequence of subgroups where each factor group is cyclic. relative_order : list The orders of factor groups of pc_series. collector : Collector By default, it is None. Collector class provides the polycyclic presentation with various other functionalities. N)pcgs pc_seriesrelative_order Collector collector)self pc_sequencer r rs Y/var/www/html/ai-engine/env/lib/python3.11/site-packages/sympy/combinatorics/pc_groups.py__init__zPolycyclicGroup.__init__ s>$  ",PYh49iHHH_hc>td|jDS)Nc34K|]}t|VdSNr).0orders r z1PolycyclicGroup.is_prime_order..$s(CCe75>>CCCCCCr)allr rs ris_prime_orderzPolycyclicGroup.is_prime_order#s"CCt/BCCCCCCrc*t|jSr)lenr rs rlengthzPolycyclicGroup.length&s49~~rr)__name__ __module__ __qualname__is_group is_solvablerrr rrr r sWHKiiii.DDDrr cbeZdZdZddZdZdZdZdZdZ d Z d Z d Z d Z d ZdZdZdS)rz References ========== .. [1] Holt, D., Eick, B., O'Brien, E. "Handbook of Computational Group Theory" Section 8.1.3 Nc.||_||_||_|s5tdt |dn||_dt |jjD|_| |_ dS)a Most of the parameters for the Collector class are the same as for PolycyclicGroup. Others are described below. Parameters ========== free_group_ : tuple free_group_ provides the mapping of polycyclic generating sequence with the free group elements. pc_presentation : dict Provides the presentation of polycyclic groups with the help of power and conjugate relators. See Also ======== PolycyclicGroup zx:{}rci|]\}}|| Sr&r&)riss r z&Collector.__init__..OsJJJtq!aJJJrN) r r r rformatr enumeratesymbolsindex pc_relatorspc_presentation)rr r r free_group_r2s rrzCollector.__init__5s, ",ITe*V]]3t99%=%=>>qAAZeJJy1H'I'IJJJ #//11rc|sdS|j}|j}|j}tt |D]=}||\}}|||r"|dks||||dz kr||ffcS>tt |dz D]A}||\}}||dz\}} ||||kr| dkrdnd} ||f|| ffcSBdS)a Returns the minimal uncollected subwords. Explanation =========== A word ``v`` defined on generators in ``X`` is a minimal uncollected subword of the word ``w`` if ``v`` is a subword of ``w`` and it has one of the following form * `v = {x_{i+1}}^{a_j}x_i` * `v = {x_{i+1}}^{a_j}{x_i}^{-1}` * `v = {x_i}^{a_j}` for `a_j` not in `\{1, \ldots, s-1\}`. Where, ``s`` is the power exponent of the corresponding generator. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics import free_group >>> G = SymmetricGroup(4) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> F, x1, x2 = free_group("x1, x2") >>> word = x2**2*x1**7 >>> collector.minimal_uncollected_subword(word) ((x2, 2),) Nr) array_formr r0ranger) rwordarrayrer0r*s1e1s2e2es rminimal_uncollected_subwordz%Collector.minimal_uncollected_subwordRsF 4   s5zz"" $ $A1XFB%)} $"q&&BE"Iq,@,@R|###s5zz!|$$ + +A1XFB1Q3ZFBRy59$$aAARR2q'****%trci}i}|jD](\}}t|jdkr|||<#|||<)||fS)a Separates the given relators of pc presentation in power and conjugate relations. Returns ======= (power_rel, conj_rel) Separates pc presentation into power and conjugate relations. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> G = SymmetricGroup(3) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> power_rel, conj_rel = collector.relations() >>> power_rel {x0**2: (), x1**3: ()} >>> conj_rel {x0**-1*x1*x0: x1**2} See Also ======== pc_relators r5)r2itemsrr7)rpower_relatorsconjugate_relatorskeyvalues r relationszCollector.relationssm<.4466 0 0JC3>""a''&+s##*/"3''111rcd}d}tt|t|z dzD]B}|||t|z|kr|}|t|z}nC||cxkrdkrnndS||fS)a Returns the start and ending index of a given subword in a word. Parameters ========== word : FreeGroupElement word defined on free group elements for a polycyclic group. w : FreeGroupElement subword of a given word, whose starting and ending index to be computed. Returns ======= (i, j) A tuple containing starting and ending index of ``w`` in the given word. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics import free_group >>> G = SymmetricGroup(4) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> F, x1, x2 = free_group("x1, x2") >>> word = x2**2*x1**7 >>> w = x2**2*x1 >>> collector.subword_index(word, w) (0, 3) >>> w = x1**7 >>> collector.subword_index(word, w) (2, 9) r6r5)r6r6)r8rsubword)rr9wlowhighr*s r subword_indexzCollector.subword_indexsPs4yyQ')**  A||AqQx((A--Qx. $    "     6Dyrc|j}|dd}|dd}|df|df|dff}|j|}|j|S)a Return a conjugate relation. Explanation =========== Given a word formed by two free group elements, the corresponding conjugate relation with those free group elements is formed and mapped with the collected word in the polycyclic presentation. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics import free_group >>> G = SymmetricGroup(3) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> F, x0, x1 = free_group("x0, x1") >>> w = x1*x0 >>> collector.map_relation(w) x1**2 See Also ======== pc_presentation rr5r6)r7rdtyper2)rrKr:r<r>rFs r map_relationzCollector.map_relations`>  1Xa[ 1Xa[Bx"a2q'*o##C((#C((rc|j} ||}|snf|||j|\}}|dkrH|d\}}t |dkr|j|j|}||z} || |zz } |dd|ff} |j| } |j| rE|j| j} | d\} }|dd| f| | |zff}|j|}n*| dkr"|dd| ff}|j|}nd}| |j||}t |dkr|dddkrs|d\}}|dff}|j|}| |j|}|||zz}|j|}| |||}nt |dkr|dddkru|d\}}|dff}|j|}| |j|}|dz||zz}|j|}| |||}|S)a Return the collected form of a word. Explanation =========== A word ``w`` is called collected, if `w = {x_{i_1}}^{a_1} * \ldots * {x_{i_r}}^{a_r}` with `i_1 < i_2< \ldots < i_r` and `a_j` is in `\{1, \ldots, {s_j}-1\}`. Otherwise w is uncollected. Parameters ========== word : FreeGroupElement An uncollected word. Returns ======= word A collected word of form `w = {x_{i_1}}^{a_1}, \ldots, {x_{i_r}}^{a_r}` with `i_1, i_2, \ldots, i_r` and `a_j \in \{1, \ldots, {s_j}-1\}`. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics.perm_groups import PermutationGroup >>> from sympy.combinatorics import free_group >>> G = SymmetricGroup(4) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> F, x0, x1, x2, x3 = free_group("x0, x1, x2, x3") >>> word = x3*x2*x1*x0 >>> collected_word = collector.collected_word(word) >>> free_to_perm = {} >>> free_group = collector.free_group >>> for sym, gen in zip(free_group.symbols, collector.pcgs): ... free_to_perm[sym] = gen >>> G1 = PermutationGroup() >>> for w in word: ... sym = w[0] ... perm = free_to_perm[sym] ... G1 = PermutationGroup([perm] + G1.generators) >>> G2 = PermutationGroup() >>> for w in collected_word: ... sym = w[0] ... perm = free_to_perm[sym] ... G2 = PermutationGroup([perm] + G2.generators) The two are not identical, but they are equivalent: >>> G1.equals(G2), G1 == G2 (True, False) See Also ======== minimal_uncollected_subword Tr6rr5N) rrArNrPrr r0r2r7eliminate_wordrQsubstituted_word)rr9rrKrLrMr<r=r;qrrF presentationsymexpword_r>r?s rcollected_wordzCollector.collected_word sB_ . ?0066A **41A1A!1D1DEEICbyyqTFB1vv{{(B8"HqtG!Q}'&j&s++', %#'#7#<#GL+AHCd1gq\C3<8E,J,U33EEAvv"#A$q'1 0 0 0 7 7 $**+;:+;A+>+>FF1vv{{qtAw{{1B1g[%Z%b))))*:**:1*=*=>>5"9 ( (//,,S$>>Q11a11B1g[%Z%b))))*:**:1*=*=>>Buby(( (//,,S$>>]. ?` rc |j}|j}i}i}|j}t||jD]\}}|dz||dz<|||<|ddd}|jddd}|ddd}g} t |D]\} }|| } ||| z} || } | || zd}||j }|D] }|||z}| |}|r|nd|| <||_ | |t| dkr| t| dz }||}tt| dz D]}|| |}|dz|z|z} |dz| |z|z}| |d}||j }|D] }|||z}| |}|r|nd|| <||_ |S)aM Return the polycyclic presentation. Explanation =========== There are two types of relations used in polycyclic presentation. * Power relations : Power relators are of the form `x_i^{re_i}`, where `i \in \{0, \ldots, \mathrm{len(pcgs)}\}`, ``x`` represents polycyclic generator and ``re`` is the corresponding relative order. * Conjugate relations : Conjugate relators are of the form `x_j^-1x_ix_j`, where `j < i \in \{0, \ldots, \mathrm{len(pcgs)}\}`. Returns ======= A dictionary with power and conjugate relations as key and their collected form as corresponding values. Notes ===== Identity Permutation is mapped with empty ``()``. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics.permutations import Permutation >>> S = SymmetricGroup(49).sylow_subgroup(7) >>> der = S.derived_series() >>> G = der[len(der)-2] >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> pcgs = PcGroup.pcgs >>> len(pcgs) 6 >>> free_group = collector.free_group >>> pc_resentation = collector.pc_presentation >>> free_to_perm = {} >>> for s, g in zip(free_group.symbols, pcgs): ... free_to_perm[s] = g >>> for k, v in pc_resentation.items(): ... k_array = k.array_form ... if v != (): ... v_array = v.array_form ... lhs = Permutation() ... for gen in k_array: ... s = gen[0] ... e = gen[1] ... lhs = lhs*free_to_perm[s]**e ... if v == (): ... assert lhs.is_identity ... continue ... rhs = Permutation() ... for gen in v_array: ... s = gen[0] ... e = gen[1] ... rhs = rhs*free_to_perm[s]**e ... assert lhs == rhs r6NToriginalr&r5)rr r zip generatorsr r.generator_productreverseidentityr\r2appendrr8)rr rel_orderr1 perm_to_freer genr+seriescollected_gensr*r;relationGlr9gconj conjugatorj conjugatedgenss rr1zCollector.pc_relatorss{F_ '   y$ 566 " "FC$%rELb ! !L  DDbDz"%dddO oo# 7# 7FAs1B#C(",Hq A##CG#==A IIKKK&D , ,LO+&&t,,D,0$8DDbK !#.D  ! !# & & &>""Q&&%c.&9&9!&;<)$/ s>22145577A!-nQ.?!@J)2~j8CH8N1$55d:D++DT+BBAIIKKK%.D44#LO3..t44D48,@DDbK)+6D((rc|j}t}|jD]}t|g|jz}||d}|i}t |j|jD]\}}|dz||dz<|||<|j}|D] }|||z}||} |j } dgt|z} | j } | D]} | d| | | d<| S)aJ Return the exponent vector of length equal to the length of polycyclic generating sequence. Explanation =========== For a given generator/element ``g`` of the polycyclic group, it can be represented as `g = {x_1}^{e_1}, \ldots, {x_n}^{e_n}`, where `x_i` represents polycyclic generators and ``n`` is the number of generators in the free_group equal to the length of pcgs. Parameters ========== element : Permutation Generator of a polycyclic group. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics.permutations import Permutation >>> G = SymmetricGroup(4) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> pcgs = PcGroup.pcgs >>> collector.exponent_vector(G[0]) [1, 0, 0, 0] >>> exp = collector.exponent_vector(G[1]) >>> g = Permutation() >>> for i in range(len(exp)): ... g = g*pcgs[i]**exp[i] if exp[i] else g >>> assert g == G[1] References ========== .. [1] Holt, D., Eick, B., O'Brien, E. "Handbook of Computational Group Theory" Section 8.1.1, Definition 8.4 Tr^r6rr5) rrr rarbrcr`rdr\r0rr7) relementrrlrnrsrgrYrKr9r0 exp_vectorts rexponent_vectorzCollector.exponent_vectors1Z_    5 5A !q|!344AA""7t"<<  */;; " "FC"%r'LB !LOO   " "A,q/!AA""1%% SZ(  + +A&'dJuQqT{ # #rc||}tdt|Dt|jdzS)a Return the depth of a given element. Explanation =========== The depth of a given element ``g`` is defined by `\mathrm{dep}[g] = i` if `e_1 = e_2 = \ldots = e_{i-1} = 0` and `e_i != 0`, where ``e`` represents the exponent-vector. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> G = SymmetricGroup(3) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> collector.depth(G[0]) 2 >>> collector.depth(G[1]) 1 References ========== .. [1] Holt, D., Eick, B., O'Brien, E. "Handbook of Computational Group Theory" Section 8.1.1, Definition 8.5 c3*K|]\}}||dzVdS)r5Nr&)rr*xs rrz"Collector.depth..`s/@@TQa@QqS@@@@@@rr5)rxnextr.rr )rrurvs rdepthzCollector.depth@sL>))'22 @@Yz%:%:@@@#di..QRBRSSSrc||}||}|t|jdzkr ||dz SdS)a  Return the leading non-zero exponent. Explanation =========== The leading exponent for a given element `g` is defined by `\mathrm{leading\_exponent}[g]` `= e_i`, if `\mathrm{depth}[g] = i`. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> G = SymmetricGroup(3) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> collector.leading_exponent(G[1]) 1 r5N)rxr}rr )rrurvr}s rleading_exponentzCollector.leading_exponentbsT*))'22  7## C NN1$ $ $eAg& &trc|}||}|t|jkr||dz dkr||dz }||||dzz}||j|dz z}|| z|z}||}|t|jkr||dz dk|S)Nr5r6)r}rr rr )rzrnhdkr@s r_siftzCollector._sift}s  JJqMM#di..  QqsVq[[!A#A%%a(($*?*?*B*BR)GGAD'!,,AA2aA 1 A #di..  QqsVq[[ rcxdgt|jz}|}|r|d}|||}||}|t|jkr7|D],}|dkr$||dz|dzz|z|z-|||dz <|d|D}|S)a8 Parameters ========== gens : list A list of generators on which polycyclic subgroup is to be defined. Examples ======== >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> S = SymmetricGroup(8) >>> G = S.sylow_subgroup(2) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> gens = [G[0], G[1]] >>> ipcgs = collector.induced_pcgs(gens) >>> [gen.order() for gen in ipcgs] [2, 2, 2] >>> G = S.sylow_subgroup(3) >>> PcGroup = G.polycyclic_group() >>> collector = PcGroup.collector >>> gens = [G[0], G[1]] >>> ipcgs = collector.induced_pcgs(gens) >>> [gen.order() for gen in ipcgs] [3] r5rr6cg|] }|dk| S)r5r&)rrhs r z*Collector.induced_pcgs..s * * *SSr)rr poprr}re)rrsrrlrnrrrhs r induced_pcgszCollector.induced_pcgss>CDI   aA 1a  A 1 A3ty>>!!66CaxxBsBwq!4555!A#  + *A * * *rcdgt|z}|}||}t|D]\}}|||krz||||z}||j|dz z}|| z|z}|||<||}|||kz|dkr|SdS)z> Return the exponent vector for induced pcgs. rr5F)rr}r.rr ) ripcgsrnr@rrr*rhfs rconstructive_membership_testz&Collector.constructive_membership_testsCE N  JJqMM&& " "FAs**S//Q&&))!,,T-B-B3-G-GG+AaC001"IaK!JJqMM **S//Q&& 66Hur)NN)r!r"r#__doc__rrArHrNrQr\r1rxr}rrrrr&rrrr*s2222:888t%2%2%2N111f$)$)$)NrrrjwwwrCCCJ T T TD6   +++ZrrN) sympy.ntheory.primetestrsympy.combinatorics.perm_groupsrsympy.printing.defaultsrsympy.combinatorics.free_groupsrr rr&rrrs++++++<<<<<<333333666666     o   F[ [ [ [ [ [ [ [ [ [ r