置换群#
- class sympy.combinatorics.perm_groups.PermutationGroup(*args, dups=True, **kwargs)[源代码]#
定义置换组的类。
解释
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.实例
>>> 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)
它们作为置换传递给置换组：
>>> 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)
或者，可以将一个置换作为所选置换的乘积，并将其直接应用于iterable：
>>> P10 = G.make_perm([0, 1]) >>> P10('ABC') ['C', 'A', 'B']
工具书类
[R62]Holt，D.，Eick，B.，O'Brien，E.《计算群理论手册》
[R63]Seress，A.“置换群算法”
[R65]https://en.wikipedia.org/wiki/Nielsen_转换
[R66]弗兰克·塞勒，查尔斯·里达姆-格林，斯科特·默里，爱丽丝·C·尼梅耶，和E.A.O'Brien。”生成有限群的随机元素”
[R69]https://en.wikipedia.org/wiki/Multiply_transitive_group#Multiply_transitive_组
- __contains__(i)[源代码]#
返回
True如果 i 包含在置换组中。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> p = Permutation(1, 2, 3) >>> Permutation(3) in PermutationGroup(p) True
- __mul__(other)[源代码]#
返回两个置换组的直积作为一个置换组。
解释
这个实现通过移动第二组生成器的索引集来实现直积：如果我们有
G作用于n1积分和H作用于n2积分，G*H作用于n1 + n2点。实例
>>> 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
- __weakref__#
list of weak references to the object
- property _elements#
以列表形式返回置换组的所有元素
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> p = PermutationGroup(Permutation(1, 3), Permutation(1, 2)) >>> p._elements [(3), (3)(1 2), (1 3), (2 3), (1 2 3), (1 3 2)]
- _eval_is_alt_sym_monte_carlo(eps=0.05, perms=None)[源代码]#
一个使用蒙特卡罗算法的测试。
- 参数:
eps ：浮动，可选
不正确的标准
False返回。烫发 ：列表 [置换] 可选
If explicitly given, it tests over the given candidates for testing.
如果
None，它随机计算N_eps选择N_eps组中排列的示例。
- _p_elements_group(p)[源代码]#
For an abelian p-group, return the subgroup consisting of all elements of order p (and the identity)
- _random_pr_init(r, n, _random_prec_n=None)[源代码]#
为产品替换算法初始化随机生成器。
解释
该实现使用了由于Leedham Green对原始产品替换算法的修改，如中所述 [1] ，第69-71页；另见 [2] ，第27-29页，对原始产品替换算法进行了详细的理论分析，以及 [4] .
乘积替换算法用于生成随机的、均匀分布的群元素 \(G\) with a set of generators \(S\). For the initialization
_ 随机初始化，一个列表 ``R属于 \(\max\{{r, |S|\}}\) 创建组生成器作为属性G._random_gens，重复的元素 \(S\) 如果需要，以及 \(G\) 被追加到R-我们将把最后一个元素称为累加器。那么函数呢random_pr()被称为n泰晤士报，随机列表R同时保留 \(G\) 通过R.功能random_pr()它本身有两个随机元素g, h在所有元素中R但是蓄能器和替代品g从中随机选择元素 \(\{{gh, g(~h), hg, (~h)g\}}\) . 然后累加器乘以g被替换为。然后由返回累加器的新值random_pr().返回的元素最终将
n足够大）变得均匀分布 \(G\) （ [5] ). 然而，出于实际目的n = 50, r = 11建议在 [1] .笔记
这个函数有副作用：它改变属性self
参见
- _sylow_alt_sym(p)[源代码]#
返回对称群或交替群的p-Sylow子群。
解释
该算法在 [1] ，第4章，练习4。
对于n=p^i的Sym（n），其思想如下。划分区间 [0..n-1] 分成p等份，每个等份长度为p^（i-1）： [0..p^(i-1)-1] ， [p^(i-1)..2*p^(i-1)-1] … [(p-1)*p^(i-1)..p^i-1] . 求Sym（p^（i-1））的p-Sylow子群（作为
self)作用于每个部分。称子群P_1，P_2…P_P。子群P_2…P_P的生成元可以通过对它们应用“移位”置换来获得，即置换映射 [0..p^(i-1)-1] 到第二部分（其他部分通过多次移位获得）。这个置换与P_1的生成元的并是self.For n not equal to a power of p, partition [0..n-1] in accordance with how n would be written in base p. E.g. for p=2 and n=11, 11 = 2^3 + 2^2 + 1 so the partition is [[0..7], [8..9], {10}]. To generate a p-Sylow subgroup, take the union of the generators for each of the parts. For the above example, {(0 1), (0 2)(1 3), (0 4), (1 5)(2 7)} from the first part, {(8 9)} from the second part and nothing from the third. This gives 4 generators in total, and the subgroup they generate is p-Sylow.
除了p=2时，交替组的处理相同。在这种情况下，应该为分区中每个部分的适当s（部分的开始）添加（01）（s s+1）。
- _union_find_merge(first, second, ranks, parents, not_rep)[源代码]#
合并联合查找数据结构中的两个类。
解释
用于Atkinson算法的实现，如 [1] ，第83-87页。类合并过程使用按秩联合作为优化。( [7] ）
笔记
这个功能有副作用：班级代表名单，
parents，类大小列表，ranks，以及不是代表的元素的列表，not_rep，由于类合并而更改。工具书类
[R71]Holt，D.，Eick，B.，O'Brien，E.《计算群理论手册》
- _union_find_rep(num, parents)[源代码]#
查找联合中类的代表查找数据结构。
解释
用于Atkinson算法的实现，如 [1] ，第83-87页。在班级代表之后
num找到属于时，将作为优化执行路径压缩( [7] ）笔记
这个功能有副作用：班级代表名单，
parents，由于路径压缩而更改。工具书类
[R73]Holt，D.，Eick，B.，O'Brien，E.《计算群理论手册》
- _verify(K, phi, z, alpha)[源代码]#
返回中继列表
rels发电机内gens`_h` that are mapped to `` H、 发电机 ``phi因此，给出了K关于gens_h<gens_h | rels_k+rels>是H.解释
H应该由K.generators和z（单个发电机），以及H.stabilizer(alpha) == K；phi是从自由群到包含H.算法在中进行了描述 [1] ，第6章。
实例
>>> from sympy.combinatorics import free_group, Permutation, PermutationGroup >>> from sympy.combinatorics.homomorphisms import homomorphism >>> from sympy.combinatorics.fp_groups import FpGroup
>>> H = PermutationGroup(Permutation(0, 2), Permutation (1, 5)) >>> K = PermutationGroup(Permutation(5)(0, 2)) >>> F = free_group("x_0 x_1")[0] >>> gens = F.generators >>> phi = homomorphism(F, H, F.generators, H.generators) >>> rels_k = [gens[0]**2] # relators for presentation of K >>> z= Permutation(1, 5) >>> check, rels_h = H._verify(K, phi, z, 1) >>> check True >>> rels = rels_k + rels_h >>> G = FpGroup(F, rels) # presentation of H >>> G.order() == H.order() True
- abelian_invariants()[源代码]#
返回给定组的交换不变量。让
G是一个非平凡有限交换群。则G同构于素数幂阶有限多个非平凡循环群的直积。解释
作为因子阶的素数幂是由G唯一决定的。更准确地说，在任何这样的分解中，以因子的顺序出现的素数幂
G正是分裂的素数|G|对于任何这样的黄金p，如果因子的阶数是p-群中的一个这样的分解G是p^{{t_1}} >= p^{{t_2}} >= ... p^{{t_r}}，则在任何这样的分解中p-群的因子的阶数G是p^{{t_1}} >= p^{{t_2}} >= ... p^{{t_r}}.唯一确定的整数
p^{{t_1}} >= p^{{t_2}} >= ... p^{{t_r}}，表示所有分裂的素数|G|称为非平凡群的不变量G如中所述( [14] ，第542页）。笔记
我们采用平凡群的不变量是[]的约定。
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.abelian_invariants() [2] >>> from sympy.combinatorics import CyclicGroup >>> G = CyclicGroup(7) >>> G.abelian_invariants() [7]
- property base#
从Schreier-Sims算法返回一个基。
解释
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.
另一种思考方式 \(B\) 它给出了包含多于同一置换的稳定陪集的指数。
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> G = PermutationGroup([Permutation(0, 1, 3)(2, 4)]) >>> G.base [0, 2]
- baseswap(base, strong_gens, pos, randomized=False, transversals=None, basic_orbits=None, strong_gens_distr=None)[源代码]#
在基和强生成集中交换两个连续的基点。
- 参数:
base, strong_gens
基础和强大的发电机组。
pos
执行交换的位置。
randomized
随机化和确定性的转换。
transversals
基本轨道的横截面，如果已知的话。
basic_orbits
基本轨道，如果知道的话。
strong_gens_distr
基本稳定器分配的强发电机，如果知道的话。
- 返回:
（基础，强根）
base是新基地，而且strong_gens是相对于它的发电机组。
解释
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.随机版本（默认）是拉斯维加斯类型。
实例
>>> 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)])
检查底座，gens是BSGS
>>> S1 = PermutationGroup(gens) >>> _verify_bsgs(S1, base, gens) True
笔记
中讨论了该算法的确定性版本 [1] ，第102-103页；随机版本在 [1] ，第103页，以及 [2] ，第98页。它是拉斯维加斯式的。注意到 [1] 在伪代码和BASESWAP的讨论中包含一个错误：在伪代码的第3行， \(|\beta_{{i+1}}^{{\left\langle T\right\rangle}}|\) 应替换为 \(|\beta_{{i}}^{{\left\langle T\right\rangle}}|\) ，并对算法进行了讨论。
- property basic_orbits#
返回与基和强生成集有关的基本轨道。
解释
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\)), thei-th basic orbit relative to this base is the orbit of \(b_i\) under \(G^{(i)}\). See [1], pp. 87-89 for more information.实例
>>> from sympy.combinatorics.named_groups import SymmetricGroup >>> S = SymmetricGroup(4) >>> S.basic_orbits [[0, 1, 2, 3], [1, 2, 3], [2, 3]]
- property basic_stabilizers#
返回相对于基础和强大发电机组的稳定器链。
解释
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.实例
>>> 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)])
- property basic_transversals#
生成强相对截集的基与基。
解释
基本断面是基本轨道的断面。它们是以字典列表的形式提供的，每个字典都有键（基本轨道的元素之一）和值（相应的横向元素）。看到了吗 [1] ，第87-89页。
实例
>>> 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)}]
- center()[源代码]#
返回置换组的中心。
解释
团体的中心 \(G\) 定义为 \(Z(G) = \{{z\in G | \forall g\in G, zg = gz \}}\) ，元素集 \(G\) 通勤的所有元素 \(G\) . 它相当于 \(G\) 里面 \(G\) ，自然是 \(G\) （ [9] ）
实例
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(4) >>> G = D.center() >>> G.order() 2
笔记
这是一个简单的实现，它是
.centralizer()参见
- centralizer(other)[源代码]#
返回组/集/元素的扶正器。
- 参数:
other
排列群/排列表/单排列
解释
一组排列的中心化子
S组内G是的元素集G通勤的所有元素S：：`C_G(S) = \{ g \in G | gs = sg \forall s \in S\}` ([10])通常，
S是G但如果G是完全对称群的真子群，我们考虑S把元素放在外面G.它自然是
G置换群的中心化子等于该群中任意一组生成元的中心化子，因为任何与生成元交换的元素都与生成元的任何乘积交换。实例
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... CyclicGroup) >>> S = SymmetricGroup(6) >>> C = CyclicGroup(6) >>> H = S.centralizer(C) >>> H.is_subgroup(C) True
笔记
实现是
.subgroup_search()使用组的特定基础进行测试G.
- commutator(G, H)[源代码]#
返回两个子群的交换子。
解释
对于置换群
K和子组G，H，的换向器G和H定义为所有换向器生成的组 \([g, h] = hgh^{{-1}}g^{{-1}}\) 对于g在里面G和h在里面H. 它自然是K（ [1] ，第27页）。实例
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... AlternatingGroup) >>> S = SymmetricGroup(5) >>> A = AlternatingGroup(5) >>> G = S.commutator(S, A) >>> G.is_subgroup(A) True
笔记
两个子群的交换子 \(H, G\) 等于所有发电机换向器的正常闭合，即。 \(hgh^{{-1}}g^{{-1}}\) 对于 \(h\) 制造者 \(H\) 和 \(g\) 制造者 \(G\) （ [1] ，第28页）
- composition_series()[源代码]#
以置换组列表的形式返回组的合成序列。
解释
群的构图序列 \(G\) 被定义为亚正态级数 \(G = H_0 > H_1 > H_2 \ldots\) 合成序列是一个次正规序列，每个因子组 \(H(i+1) / H(i)\) 很简单。次正态级数只有在其最大长度时才是合成级数。
该算法的工作原理如下：从派生序列开始，其思想是填补两者之间的空白 \(G = der[i]\) 和 \(H = der[i+1]\) 对于每一个 \(i\) 独立地。因为，阿贝尔群的所有子群 \(G/H\) 都是正常的，所以，第一步是启动发电机 \(g\) 属于 \(G\) 并将它们添加到 \(H\) 逐一地。
形成的因素组一般不简单。每组通过添加一个生成器从前一个组中获取 \(g\) ，如果前一组用 \(H\) 然后是下一组 \(K\) 由生成 \(g\) 和 \(H\) . 因素组 \(K/H\) 是循环的，它的顺序是 \(K.order()//G.order()\) . 然后将序列扩展到 \(K\) 和 \(H\) 由权力产生的集团 \(g\) 和 \(H\) . 然后将形成的系列添加到已存在的系列之前。
实例
>>> 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]
- conjugacy_class(x)[源代码]#
返回组中元素的共轭类。
解释
元素的共轭类
g集体G是一组元素x在里面G与g，即g = xax^{-1}对某些人来说
a在里面G.注意共轭是一个等价关系，因此共轭类是
G. 对于组的所有共轭类的列表，请使用共轭类（）方法。在置换群中，每个共轭类对应于一个特定的 \(cycle structure': for example, in ` `S_3`\)，共轭类是：
身份等级，
{{()}}所有的换位，
{{(1 2), (1 3), (2 3)}}所有3个循环，
{{(1 2 3), (1 3 2)}}
实例
>>> from sympy.combinatorics import Permutation, SymmetricGroup >>> S3 = SymmetricGroup(3) >>> S3.conjugacy_class(Permutation(0, 1, 2)) {(0 1 2), (0 2 1)}
笔记
这个过程通过寻找G中共轭元素的轨道，直接计算共轭类。该算法只适用于阶数相对较小的置换群，但在这方面类似于orbit（）函数本身。
- conjugacy_classes()[源代码]#
返回组的共轭类。
解释
如.conjugacy_class（）函数的文档中所述，conjugacy是对元素集进行分区的组G上的等价关系。这个方法返回G的所有共轭类的列表。
实例
>>> from sympy.combinatorics import SymmetricGroup >>> SymmetricGroup(3).conjugacy_classes() [{(2)}, {(0 1 2), (0 2 1)}, {(0 2), (1 2), (2)(0 1)}]
- contains(g, strict=True)[源代码]#
测试是否排列
g属于自己，G.解释
如果
g是的元素G它可以写成从G的稳定器。看看g是定义组使用的实际生成器之一G.has(g).如果
strict不是True，g如果需要，将调整大小以匹配self.实例
>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> a = Permutation(1, 2) >>> b = Permutation(2, 3, 1) >>> G = PermutationGroup(a, b, degree=5) >>> G.contains(G[0]) # trivial check True >>> elem = Permutation([[2, 3]], size=5) >>> G.contains(elem) True >>> G.contains(Permutation(4)(0, 1, 2, 3)) False
如果strict为False，则将调整置换的大小（如有必要）：
>>> H = PermutationGroup(Permutation(5)) >>> H.contains(Permutation(3)) False >>> H.contains(Permutation(3), strict=False) True
要测试组中是否存在给定的置换：
>>> elem in G.generators False >>> G.has(elem) False
- coset_factor(g, factor_index=False)[源代码]#
返回
G的陪集分解g解释
如果
g是的元素G然后它可以写为从Schreier-Sims陪集分解得到的置换的乘积，排列又回来了
f是产品提供的g：g = f[n]*...f[1]*f[0]在哪里？n = len(B)和B = G.base. f [i] 是self._basic_orbits[i].如果因子u index==True，则返回元组
[b[0],..,b[n]]在哪里b[i]属于self._basic_orbits[i]实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(0, 1, 3, 7, 6, 4)(2, 5) >>> b = Permutation(0, 1, 3, 2)(4, 5, 7, 6) >>> G = PermutationGroup([a, b])
定义g：
>>> g = Permutation(7)(1, 2, 4)(3, 6, 5)
确认它是G的一个元素：
>>> G.contains(g) True
因此，它可以写为从u提取的因子（最多3个）的乘积。如下所示，使用了u1和u2的因子和同一置换：
>>> f = G.coset_factor(g) >>> f[2]*f[1]*f[0] == g True >>> f1 = G.coset_factor(g, True); f1 [0, 4, 4] >>> tr = G.basic_transversals >>> f[0] == tr[0][f1[0]] True
如果g不是g的元素，则返回[]：
>>> c = Permutation(5, 6, 7) >>> G.coset_factor(c) []
- coset_rank(g)[源代码]#
使用Schreier-Sims表示进行排名。
解释
宠儿等级
g是根据coset分解在词典列表中显示的顺序号其顺序与G.generate（method='coset'）中的顺序相同。如果
g不属于组，它返回None。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(0, 1, 3, 7, 6, 4)(2, 5) >>> b = Permutation(0, 1, 3, 2)(4, 5, 7, 6) >>> G = PermutationGroup([a, b]) >>> c = Permutation(7)(2, 4)(3, 5) >>> G.coset_rank(c) 16 >>> G.coset_unrank(16) (7)(2 4)(3 5)
参见
- property degree#
返回组中置换的大小。
解释
组成群的置换数由
len(group)；可由组生成的置换数由group.order().实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 0, 2]) >>> G = PermutationGroup([a]) >>> G.degree 3 >>> len(G) 1 >>> G.order() 2 >>> list(G.generate()) [(2), (2)(0 1)]
参见
- derived_series()[源代码]#
返回组的派生序列。
- 返回:
包含派生的成员的置换群的列表
顺序中的系列 \(G = G_0, G_1, G_2, \ldots\) .
解释
群的派生级数 \(G\) 定义为 \(G = G_0 > G_1 > G_2 > \ldots\) 在哪里？ \(G_i = [G_{{i-1}}, G_{{i-1}}]\) ，即 \(G_i\) 的派生子群 \(G_{{i-1}}\) ，为了 \(i\in\mathbb{{N}}\) . 当我们有 \(G_k = G_{{k-1}}\) 对某些人来说 \(k\in\mathbb{{N}}\) ，序列终止。
实例
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... AlternatingGroup, DihedralGroup) >>> A = AlternatingGroup(5) >>> len(A.derived_series()) 1 >>> S = SymmetricGroup(4) >>> len(S.derived_series()) 4 >>> S.derived_series()[1].is_subgroup(AlternatingGroup(4)) True >>> S.derived_series()[2].is_subgroup(DihedralGroup(2)) True
- derived_subgroup()[源代码]#
计算派生子群。
解释
派生子群或交换子群是由所有交换子生成的子群 \([g, h] = hgh^{{-1}}g^{{-1}}\) 对于 \(g, h\in G\) 等于发电机换向器组的正常闭合( [1] ，第28页， [11] ）
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 0, 2, 4, 3]) >>> b = Permutation([0, 1, 3, 2, 4]) >>> G = PermutationGroup([a, b]) >>> C = G.derived_subgroup() >>> list(C.generate(af=True)) [[0, 1, 2, 3, 4], [0, 1, 3, 4, 2], [0, 1, 4, 2, 3]]
- property elements#
以集合的形式返回置换组的所有元素
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> p = PermutationGroup(Permutation(1, 3), Permutation(1, 2)) >>> p.elements {(1 2 3), (1 3 2), (1 3), (2 3), (3), (3)(1 2)}
- equals(other)[源代码]#
返回
True如果组中元素生成的置换组是相同的，即它们表示相同的置换组。实例
>>> 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
- generate(method='coset', af=False)[源代码]#
返回iterator以生成组的元素。
解释
使用以下方法之一进行迭代：
method='coset' using the Schreier-Sims coset representation method='dimino' using the Dimino method
如果
af = True它产生排列的数组形式实例
>>> from sympy.combinatorics import PermutationGroup >>> from sympy.combinatorics.polyhedron import tetrahedron
四面体对象中给出的置换群也是真群：
>>> G = tetrahedron.pgroup >>> G.is_group True
同样，由四面体pgroup中的置换生成的群——甚至前两个——也是一个恰当的群：
>>> H = PermutationGroup(G[0], G[1]) >>> J = PermutationGroup(list(H.generate())); J PermutationGroup([ (0 1)(2 3), (1 2 3), (1 3 2), (0 3 1), (0 2 3), (0 3)(1 2), (0 1 3), (3)(0 2 1), (0 3 2), (3)(0 1 2), (0 2)(1 3)]) >>> _.is_group True
- generate_dimino(af=False)[源代码]#
使用Dimino算法生成群元素。
如果
af == True它产生排列的数组形式。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([0, 2, 3, 1]) >>> g = PermutationGroup([a, b]) >>> list(g.generate_dimino(af=True)) [[0, 1, 2, 3], [0, 2, 1, 3], [0, 2, 3, 1], [0, 1, 3, 2], [0, 3, 2, 1], [0, 3, 1, 2]]
工具书类
[R75]计算机代数系统中置换群各种算法的实现：AXIOM，N.J.Doye，M.Sc.论文
- generate_schreier_sims(af=False)[源代码]#
用陪集秩序Schreier-Sims表示的屈服群元
如果
af = True它产生排列的数组形式实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([0, 2, 3, 1]) >>> g = PermutationGroup([a, b]) >>> list(g.generate_schreier_sims(af=True)) [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 2, 1], [0, 1, 3, 2], [0, 2, 3, 1], [0, 3, 1, 2]]
- generator_product(g, original=False)[源代码]#
Return a list of strong generators \([s1, \dots, sn]\) s.t \(g = sn \times \dots \times s1\). If
original=True, make the list contain only the original group generators
- property generators#
返回组的生成器。
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.generators [(1 2), (2)(0 1)]
- property identity#
返回置换组的标识元素。
- index(H)[源代码]#
返回置换组的索引。
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(1,2,3) >>> b =Permutation(3) >>> G = PermutationGroup([a]) >>> H = PermutationGroup([b]) >>> G.index(H) 3
- property is_abelian#
测试组是否是交换的。
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.is_abelian False >>> a = Permutation([0, 2, 1]) >>> G = PermutationGroup([a]) >>> G.is_abelian True
- is_alt_sym(eps=0.05, _random_prec=None)[源代码]#
度>=8时对称/交替群的蒙特卡罗检验。
解释
更具体地说，它是单面蒙特卡罗，答案为真（即G是对称的/交替的）保证是正确的，而答案为False的概率eps是不正确的。
如果阶数小于8，则检查组的顺序，因此测试是确定性的。
笔记
算法本身使用了群论和数论的一些重要结果：1）如果是传递群
G程度的n包含长度为循环的元素n/2 < p < n-2对于p一个质数，G是对称群还是交替群( [1] ，第81-82页）2）具有1）所述性质的对称/交替群中元素的比例约为 \(\log(2)/\log(n)\) ([1], p.82; [2], pp. 226-227). The helper function ``_ check_cycles_alt_sym``用于遍历排列中的循环并查找满足1）的循环。实例
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(10) >>> D.is_alt_sym() False
- property is_alternating#
返回
True如果组是交替的。实例
>>> from sympy.combinatorics import AlternatingGroup >>> g = AlternatingGroup(5) >>> g.is_alternating True
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> g = PermutationGroup( ... Permutation(0, 1, 2, 3, 4), ... Permutation(2, 3, 4)) >>> g.is_alternating True
笔记
这使用了一个简单的测试，涉及到整个组顺序的计算。如果您需要对大型组进行更快速的分类，可以使用
PermutationGroup.is_alt_sym(). 然而，PermutationGroup.is_alt_sym()可能不准确，无法区分交替群和对称群。参见
- property is_cyclic#
返回
True如果组是循环的。实例
>>> from sympy.combinatorics.named_groups import AbelianGroup >>> G = AbelianGroup(3, 4) >>> G.is_cyclic True >>> G = AbelianGroup(4, 4) >>> G.is_cyclic False
笔记
If the order of a group \(n\) can be factored into the distinct primes \(p_1, p_2, \dots , p_s\) and if
\[\forall i, j \in \{1, 2, \dots, s \}: p_i \not \equiv 1 \pmod {p_j}\]holds true, there is only one group of the order \(n\) which is a cyclic group [R76]. This is a generalization of the lemma that the group of order \(15, 35, \dots\) are cyclic.
另外，这些附加引理还可以用来测试一个群是否是循环的，如果已经找到了这个群的阶数。
如果群是交换的且群的阶是无平方的，则群是循环的。
如果组的顺序小于\(6\)，而不是\(4\)，则该组是循环的。
素群的阶是循环的。
工具书类
- property is_dihedral#
Return
Trueif the group is dihedral.实例
>>> from sympy.combinatorics.perm_groups import PermutationGroup >>> from sympy.combinatorics.permutations import Permutation >>> from sympy.combinatorics.named_groups import SymmetricGroup, CyclicGroup >>> G = PermutationGroup(Permutation(1, 6)(2, 5)(3, 4), Permutation(0, 1, 2, 3, 4, 5, 6)) >>> G.is_dihedral True >>> G = SymmetricGroup(3) >>> G.is_dihedral True >>> G = CyclicGroup(6) >>> G.is_dihedral False
工具书类
[Di1]
- is_elementary(p)[源代码]#
返回
True如果这个群是初等的abelian。初等abelian群是一个有限abelian群，其中每个非平凡单元都有阶 \(p\) 在哪里 \(p\) 是一个质数。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> G = PermutationGroup([a]) >>> G.is_elementary(2) True >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([3, 1, 2, 0]) >>> G = PermutationGroup([a, b]) >>> G.is_elementary(2) True >>> G.is_elementary(3) False
- property is_nilpotent#
检验群是否幂零。
解释
一群人 \(G\) 如果它有一个有限长度的中心级数，则它是幂零的。或者， \(G\) 如果其下中心级数以平凡群终止，则为幂零。每个幂零群也是可解的( [1] ，第29页， [12] ）
实例
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... CyclicGroup) >>> C = CyclicGroup(6) >>> C.is_nilpotent True >>> S = SymmetricGroup(5) >>> S.is_nilpotent False
- is_normal(gr, strict=True)[源代码]#
测试是否
G=self是的正规子群gr.解释
G在gr中是正常的，如果G中的每个g2，g1在gr中，
g = g1*g2*g1**-1属于G，对每个g1英寸进行检查就足够了发电机组和g2发电机。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 2, 0]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G1 = PermutationGroup([a, Permutation([2, 0, 1])]) >>> G1.is_normal(G) True
- property is_perfect#
返回
True如果团队是完美的。如果一个群等于它的派生子群，它就是完美的。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(1,2,3)(4,5) >>> b = Permutation(1,2,3,4,5) >>> G = PermutationGroup([a, b]) >>> G.is_perfect False
- property is_polycyclic#
返回
True如果一个群是多环的。如果一个群有一个带循环因子的次正态级数，则它是多环的。对于有限群，这和群是可解的是一样的。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([2, 0, 1, 3]) >>> G = PermutationGroup([a, b]) >>> G.is_polycyclic True
- is_primitive(randomized=True)[源代码]#
测试组是否为基元。
解释
置换群
G在布景上表演S称为基元ifS在的操作下不包含非平凡块G（如果块的基数大于1）笔记
算法在中进行了描述 [1] ，第83页，并使用函数minimal_block搜索表单的块 \(\{{0, k\}}\) 对于
k在轨道上的代表 \(G_0\) ，稳定剂0. 该算法具有复杂性 \(O(n^2)\) 在哪里？n是组的程度，如果 \(G_0\) 很小。提供了两种实现：一种是 \(G_0\) 确定地使用函数
stabilizer，另一个（默认）生成 \(G_0\) 使用random_stab希望他们能产生一个 \(G_0\) 轨道不比 \(G_0\) （建议参见 [1] ，第83页）。行为被randomized旗帜。实例
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(10) >>> D.is_primitive() False
- property is_solvable#
检验群是否可解。
G如果其导级数以平凡群终止，则是可解的( [1] 第29页）。实例
>>> from sympy.combinatorics.named_groups import SymmetricGroup >>> S = SymmetricGroup(3) >>> S.is_solvable True
- is_subgroup(G, strict=True)[源代码]#
返回
True如果所有元素self属于G.如果
strict是False那么如果self的学位比G这些元素的大小将调整为相同的程度。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> from sympy.combinatorics import SymmetricGroup, CyclicGroup
测试默认严格：每组的程度必须相同：
>>> p = Permutation(0, 1, 2, 3, 4, 5) >>> G1 = PermutationGroup([Permutation(0, 1, 2), Permutation(0, 1)]) >>> G2 = PermutationGroup([Permutation(0, 2), Permutation(0, 1, 2)]) >>> G3 = PermutationGroup([p, p**2]) >>> assert G1.order() == G2.order() == G3.order() == 6 >>> G1.is_subgroup(G2) True >>> G1.is_subgroup(G3) False >>> G3.is_subgroup(PermutationGroup(G3[1])) False >>> G3.is_subgroup(PermutationGroup(G3[0])) True
设置为忽略大小
strict到False：>>> S3 = SymmetricGroup(3) >>> S5 = SymmetricGroup(5) >>> S3.is_subgroup(S5, strict=False) True >>> C7 = CyclicGroup(7) >>> G = S5*C7 >>> S5.is_subgroup(G, False) True >>> C7.is_subgroup(G, 0) False
- property is_symmetric#
返回
True如果组是对称的。实例
>>> from sympy.combinatorics import SymmetricGroup >>> g = SymmetricGroup(5) >>> g.is_symmetric True
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> g = PermutationGroup( ... Permutation(0, 1, 2, 3, 4), ... Permutation(2, 3)) >>> g.is_symmetric True
笔记
这使用了一个简单的测试，涉及到整个组顺序的计算。如果您需要对大型组进行更快速的分类，可以使用
PermutationGroup.is_alt_sym(). 然而，PermutationGroup.is_alt_sym()可能不准确，无法区分交替群和对称群。参见
- is_transitive(strict=True)[源代码]#
测试组是否可传递。
解释
如果一个群只有一个轨道，那么它是可传递的。
如果
strict是False如果一个轨道的长度与1不同，则该群是传递的。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1, 3]) >>> b = Permutation([2, 0, 1, 3]) >>> G1 = PermutationGroup([a, b]) >>> G1.is_transitive() False >>> G1.is_transitive(strict=False) True >>> c = Permutation([2, 3, 0, 1]) >>> G2 = PermutationGroup([a, c]) >>> G2.is_transitive() True >>> d = Permutation([1, 0, 2, 3]) >>> e = Permutation([0, 1, 3, 2]) >>> G3 = PermutationGroup([d, e]) >>> G3.is_transitive() or G3.is_transitive(strict=False) False
- property is_trivial#
测试组是否是平凡组。
如果组只包含标识置换，则这是正确的。
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> G = PermutationGroup([Permutation([0, 1, 2])]) >>> G.is_trivial True
- lower_central_series()[源代码]#
返回组的下中心序列。
群的下中心级数 \(G\) 是系列 \(G = G_0 > G_1 > G_2 > \ldots\) 在哪里？ \(G_k = [G, G_{{k-1}}]\) ，即第一项后的每项都等于 \(G\) 上一学期 \(G1\) （ [1] 第29页）。
- 返回:
按顺序排列的排列组的列表 \(G = G_0, G_1, G_2, \ldots\)
实例
>>> from sympy.combinatorics.named_groups import (AlternatingGroup, ... DihedralGroup) >>> A = AlternatingGroup(4) >>> len(A.lower_central_series()) 2 >>> A.lower_central_series()[1].is_subgroup(DihedralGroup(2)) True
- make_perm(n, seed=None)[源代码]#
乘法
n从pgroup中随机选择排列在一起，从标识置换开始。如果n是一个整数列表，这些整数将用于选择置换，并按L到R的顺序应用：make_perm（（a，B，C））将给出CBA（I），其中I是标识置换。seed从粒子群到粒子群的随机选择。如果这是一个整数列表，则将按照给定的顺序从pgroup中选择相应的置换。这主要用于测试目的。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a, b = [Permutation([1, 0, 3, 2]), Permutation([1, 3, 0, 2])] >>> G = PermutationGroup([a, b]) >>> G.make_perm(1, [0]) (0 1)(2 3) >>> G.make_perm(3, [0, 1, 0]) (0 2 3 1) >>> G.make_perm([0, 1, 0]) (0 2 3 1)
参见
- property max_div#
置换群度的最大真除数。
解释
显然，这是度除以它的最小真除数（大于
1，如果存在）。因为它保证是优质的sieve从sympy.ntheory已使用。此函数还用作函数的优化工具minimal_block和_union_find_merge.实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> G = PermutationGroup([Permutation([0, 2, 1, 3])]) >>> G.max_div 2
- minimal_block(points)[源代码]#
对于传递组，查找由生成的块系统
points.解释
If a group
Gacts on a setS, a nonempty subsetBofSis called a block under the action ofGif for allginGwe havegB = B(gfixesB) orgBandBhave no common points (gmovesBentirely). ([1], p.23; [6]).不同的翻译
gB一个街区的B对于g在里面G划分集合S这组翻译被称为块系统。而且，显然，分区中的所有块都具有相同的大小，因此块大小被划分|S|（ [1] ，第23页）。AG-同余是一个等价关系~在片场S这样的话a ~ b暗示g(a) ~ g(b)为了所有g在里面G. 对于传递群，a的等价类G-同余和块系统的块是一回事( [1] ，第23页）。下面的算法检查组的传递性，然后找到
G-对生成的同余(p_0, p_1), (p_0, p_2), ..., (p_0,p_{{k-1}})这与求最大块系统（即块大小最小的块系统）相同，使得p_0, ..., p_{{k-1}}在同一个街区( [1] ，第83页）。它是Atkinson算法的一个实现，如 [1] ，并处理集合上的等价关系
S使用联合查找数据结构。运行时间刚好在上面 \(O(|points||S|)\) . （ [1] ，第83-87页； [7] ）实例
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(10) >>> D.minimal_block([0, 5]) [0, 1, 2, 3, 4, 0, 1, 2, 3, 4] >>> D.minimal_block([0, 1]) [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
- minimal_blocks(randomized=True)[源代码]#
对于可传递组，返回所有最小块系统的列表。如果组是不可传递的，则返回 \(False\) .
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> from sympy.combinatorics.named_groups import DihedralGroup >>> DihedralGroup(6).minimal_blocks() [[0, 1, 0, 1, 0, 1], [0, 1, 2, 0, 1, 2]] >>> G = PermutationGroup(Permutation(1,2,5)) >>> G.minimal_blocks() False
- normal_closure(other, k=10)[源代码]#
返回子组/置换集的正规闭包。
- 参数:
other
一个子组/排列列表/单个排列
k
一种特定于实现的参数，用于确定连接到
other马上
解释
如果
S是组的子集G，正常闭合A在里面G定义为所有正规子群的交集G包含A（ [1] ，第14页）。或者，它是由共轭物生成的基团x^{{-1}}yx对于x制造者G和y子群的生成元\left\langle S\right\rangle生成的S（对于某些选定的发电机组\left\langle S\right\rangle（ [1] ，第73页）。实例
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... CyclicGroup, AlternatingGroup) >>> S = SymmetricGroup(5) >>> C = CyclicGroup(5) >>> G = S.normal_closure(C) >>> G.order() 60 >>> G.is_subgroup(AlternatingGroup(5)) True
笔记
算法在中进行了描述 [1] 第73-74页；它利用乘积置换算法生成置换群的随机元素。
- orbit(alpha, action='tuples')[源代码]#
计算α轨道 \(\{{g(\alpha) | g \in G\}}\) 作为一套。
解释
这里使用的算法的时间复杂度是 \(O(|Orb|*r)\) 在哪里？ \(|Orb|\) 是轨道的大小
r是组的生成器数。有关更详细的分析，请参见 [1] ，第78页， [2] ，第19-21页。这里alpha可以是一个点，也可以是一个点的列表。如果α是单点，则计算普通轨道。如果alpha是点列表，则有三个可用选项：
“并集”-计算列表“元组”中点轨道的并集-计算在组操作下被解释为有序元组的列表的轨道（例如，g（（1,2,3））=（g（1），g（2），g（3））“集”-计算被解释为集的列表的轨道
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 2, 0, 4, 5, 6, 3]) >>> G = PermutationGroup([a]) >>> G.orbit(0) {0, 1, 2} >>> G.orbit([0, 4], 'union') {0, 1, 2, 3, 4, 5, 6}
- orbit_rep(alpha, beta, schreier_vector=None)[源代码]#
返回发送
alpha到beta.解释
如果
beta不在轨道上alpha，函数返回False. 这个实现使用了schreier向量。有关正确性的证明，请参见 [1] ，第80页实例
>>> from sympy.combinatorics.named_groups import AlternatingGroup >>> G = AlternatingGroup(5) >>> G.orbit_rep(0, 4) (0 4 1 2 3)
- orbit_transversal(alpha, pairs=False)[源代码]#
计算轨道的横截面
alpha作为一套。解释
对于置换群 \(G\) 轨道的横截面 \(Orb = \{{g(\alpha) | g \in G\}}\) 是一套 \(\{{g_\beta | g_\beta(\alpha) = \beta\}}\) 对于 \(\beta \in Orb\) . 请注意，可能有多个可能的横截面。如果
pairs设置为True，它返回对的列表 \((\beta, g_\beta)\) . 有关正确性的证明，请参见 [1] ，第79页实例
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> G = DihedralGroup(6) >>> G.orbit_transversal(0) [(5), (0 1 2 3 4 5), (0 5)(1 4)(2 3), (0 2 4)(1 3 5), (5)(0 4)(1 3), (0 3)(1 4)(2 5)]
参见
- orbits(rep=False)[源代码]#
返回的轨道
self，按每个轨道的最低元素排序。实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation(1, 5)(2, 3)(4, 0, 6) >>> b = Permutation(1, 5)(3, 4)(2, 6, 0) >>> G = PermutationGroup([a, b]) >>> G.orbits() [{0, 2, 3, 4, 6}, {1, 5}]
- order()[源代码]#
返回组的顺序：可以从组的元素生成的置换数。
组成群的置换数由
len(group)；组中每个排列的长度由group.size.实例
>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> a = Permutation([1, 0, 2]) >>> G = PermutationGroup([a]) >>> G.degree 3 >>> len(G) 1 >>> G.order() 2 >>> list(G.generate()) [(2), (2)(0 1)]
>>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.order() 6
参见
- pointwise_stabilizer(points, incremental=True)[源代码]#
返回一组点的逐点稳定器。
解释
对于置换群 \(G\) 还有一系列要点 \(\{{p_1, p_2,\ldots, p_k\}}\) ，点态稳定器 \(p_1, p_2, \ldots, p_k\) 定义为 \(G_{{p_1,\ldots, p_k}} = \{{g\in G | g(p_i) = p_i \forall i\in\{{1, 2,\ldots,k\}}\}}\) （ [1] ，第20页）。它是 \(G\) .
实例
>>> from sympy.combinatorics.named_groups import SymmetricGroup >>> S = SymmetricGroup(7) >>> Stab = S.pointwise_stabilizer([2, 3, 5]) >>> Stab.is_subgroup(S.stabilizer(2).stabilizer(3).stabilizer(5)) True
笔记
当incremental==True时，而不是使用连续调用
.stabilizer()本文采用增量式Schreier-Sims算法得到一个以起始段为基的给定点。
- polycyclic_group()[源代码]#
使用以下参数返回polycycycroup实例：
解释
pc_sequence : Polycyclic sequence is formed by collecting all the missing generators between the adjacent groups in the derived series of given permutation group.
pc_series : Polycyclic series is formed by adding all the missing generators of
der[i+1]inder[i], wherederrepresents the derived series.relative_order : A list, computed by the ratio of adjacent groups in pc_series.
- random_pr(gen_count=11, iterations=50, _random_prec=None)[源代码]#
使用产品替换返回随机组元素。
解释
有关产品替换算法的详细信息，请参阅
_random_pr_init在random_pr执行实际的“产品更换”。注意如果属性_random_gens为空，需要由初始化_random_pr_init.
- random_stab(alpha, schreier_vector=None, _random_prec=None)[源代码]#
来自稳定塔的随机元素
alpha.的schreier向量
alpha是用于加速重复呼叫的可选参数。算法在中进行了描述 [1] ，第81页
- schreier_sims()[源代码]#
SchreierSims算法。
解释
它计算稳定器链的生成器 \(G > G_{{b_1}} > .. > G_{{b1,..,b_r}} > 1\) 在哪儿 \(G_{{b_1,..,b_i}}\) 稳定 \(b_1,..,b_i\) ，以及相应的
s陪衬。组的一个元素可以写成产品 \(h_1*..*h_s\) .我们使用增量Schreier-Sims算法。
实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([0, 2, 1]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.schreier_sims() >>> G.basic_transversals [{0: (2)(0 1), 1: (2), 2: (1 2)}, {0: (2), 2: (0 2)}]
- schreier_sims_incremental(base=None, gens=None, slp_dict=False)[源代码]#
将点序列和生成集扩展为基强生成集。
- 参数:
base
扩展到基的点的序列。带默认值的可选参数
[].gens
将生成集扩展为相对于基的强生成集。带默认值的可选参数
self.generators.slp_dict
如果 \(True\) ，返回字典 \({{g: gens}}\) 对于每台强发电机 \(g\) 在哪里？ \(gens\) 有没有一份强大的发电机的清单 \(g\) 在里面 \(strong_gens\) ，使得元素的乘积 \(gens\) 等于 \(g\) .
- 返回:
（基础，强根）
base是否获得基数，以及strong_gens是相对于它的强大的发电机组。原始参数base，gens保持不变。
实例
>>> from sympy.combinatorics.named_groups import AlternatingGroup >>> from sympy.combinatorics.testutil import _verify_bsgs >>> A = AlternatingGroup(7) >>> base = [2, 3] >>> seq = [2, 3] >>> base, strong_gens = A.schreier_sims_incremental(base=seq) >>> _verify_bsgs(A, base, strong_gens) True >>> base[:2] [2, 3]
笔记
这个版本的Schreier-Sims算法在多项式时间内运行。在实现中有一些假设-如果提供了琐碎的组，
base和gens立即返回，因为任何点序列都是平凡组的基。如果生成器中存在身份gens，因为它是一个冗余的生成器，所以被删除。实现如中所述 [1] ，第90-93页。
- schreier_sims_random(base=None, gens=None, consec_succ=10, _random_prec=None)[源代码]#
随机Schreier-Sims算法。
- 参数:
base
延伸到基部的序列。
gens
将生成集扩展为强生成集。
consec_succ
定义错误答案概率的参数。
_random_prec
用于测试目的的内部参数。
- 返回:
（基础，强根）
base是基地和strong_gens是相对于它的强大的发电机组。
解释
随机Schreier-Sims算法取序列
base以及发电机组gens，并延伸base到一个基地，然后gens对于一个强的发电机组相对于那个基地，最多有一个错误答案的概率 \(2^{{-consec\_succ}}\) ，前提是随机生成器足够随机。实例
>>> from sympy.combinatorics.testutil import _verify_bsgs >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> S = SymmetricGroup(5) >>> base, strong_gens = S.schreier_sims_random(consec_succ=5) >>> _verify_bsgs(S, base, strong_gens) True
笔记
详细描述了该算法 [1] ，第97-98页。它延伸了轨道
orbs以及置换群stabs以基本轨道和基本稳定器为基础，最终产生了强发电机组。扩展过程的思想是通过稳定链“筛选”随机群元素，并在筛选不成功时修正稳定器/轨道。helper函数_strip用于尝试根据稳定链的当前状态分解随机组元素，并报告该元素是否已完全分解（sift成功）或未完全分解（sift失败）。在后一种情况下，将报告sift失败的级别，并用于修正stabs，base，gens和orbs因此。停止状态是为了consec_succ连续成功筛选通过。这样可以确保电流base和gens形成一个至少有概率的BSGS \(1 - 1/\text{{consec\_succ}}\) .
- schreier_vector(alpha)[源代码]#
计算
alpha.解释
The Schreier vector efficiently stores information about the orbit of
alpha. It can later be used to quickly obtain elements of the group that sendalphato a particular element in the orbit. Notice that the Schreier vector depends on the order in which the group generators are listed. For a definition, see [3]. Since list indices start from zero, we adopt the convention to use "None" instead of 0 to signify that an element does not belong to the orbit. For the algorithm and its correctness, see [2], pp.78-80.实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([2, 4, 6, 3, 1, 5, 0]) >>> b = Permutation([0, 1, 3, 5, 4, 6, 2]) >>> G = PermutationGroup([a, b]) >>> G.schreier_vector(0) [-1, None, 0, 1, None, 1, 0]
参见
- stabilizer(alpha)[源代码]#
返回的稳定子组
alpha.解释
稳定器 \(\alpha\) 是团体吗 \(G_\alpha = \{{g \in G | g(\alpha) = \alpha\}}\) . 有关正确性的证明，请参见 [1] ，第79页。
实例
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> G = DihedralGroup(6) >>> G.stabilizer(5) PermutationGroup([ (5)(0 4)(1 3)])
参见
- property strong_gens#
从Schreier-Sims算法返回一个强生成集。
解释
A generating set \(S = \{g_1, g_2, \dots, g_t\}\) for a permutation group \(G\) is a strong generating set relative to the sequence of points (referred to as a "base") \((b_1, b_2, \dots, b_k)\) if, for \(1 \leq i \leq k\) we have that the intersection of the pointwise stabilizer \(G^{(i+1)} := G_{b_1, b_2, \dots, b_i}\) with \(S\) generates the pointwise stabilizer \(G^{(i+1)}\). 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.
实例
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> D = DihedralGroup(4) >>> D.strong_gens [(0 1 2 3), (0 3)(1 2), (1 3)] >>> D.base [0, 1]
- strong_presentation()[源代码]#
Return a strong finite presentation of group. The generators of the returned group are in the same order as the strong generators of group.
该算法基于中描述的Sims验证算法 [1] ，第6章。
实例
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> P = DihedralGroup(4) >>> G = P.strong_presentation() >>> P.order() == G.order() True
参见
- subgroup_search(prop, base=None, strong_gens=None, tests=None, init_subgroup=None)[源代码]#
找到满足属性的所有元素的子组
prop.- 参数:
prop
要使用的属性。必须对组元素调用并始终返回
True或False. 假设所有群元素满足prop确实形成了一个小群体。base
超级群的基地。
strong_gens
超群的强生成集。
tests
长度等于
base. 这些用于排除部分基本图像的组元素，以便tests[l](g)如果元素g已知不满足道具基地在哪里g发送第一个l + 1基点。init_subgroup
如果预先知道所查找组的子组，则可以将其作为此参数传递给函数。
- 返回:
物件
满足条件的所有元素的子群
prop. 此组的生成集保证是相对于基的强生成集base.
解释
这是通过对基本图像进行深度优先搜索来完成的，它使用几个测试来修剪搜索树。
实例
>>> from sympy.combinatorics.named_groups import (SymmetricGroup, ... AlternatingGroup) >>> from sympy.combinatorics.testutil import _verify_bsgs >>> S = SymmetricGroup(7) >>> prop_even = lambda x: x.is_even >>> base, strong_gens = S.schreier_sims_incremental() >>> G = S.subgroup_search(prop_even, base=base, strong_gens=strong_gens) >>> G.is_subgroup(AlternatingGroup(7)) True >>> _verify_bsgs(G, base, G.generators) True
笔记
这个功能非常冗长和复杂，需要特别注意。实现如中所述 [1] ，第114-117页，为了清晰起见，这里的代码注释遵循书中伪代码的行。
一般来说，复杂度是指数级的，因为搜索过程本身会访问超组的所有成员。但是，有很多测试被用来修剪搜索树，用户可以通过
tests参数，所以在实践中，对于一些计算来说，这并不可怕。该过程中的一个关键部分是为了获得一个新的基本稳定器而进行的频繁的基极改变（这是伪代码中的第11行）。书中提到这可以通过使用
.baseswap(...)然而，当前的实现使用一种更直接的方法来找到下一个基本稳定器-调用函数.stabilizer(...)在之前的基本稳定器上。
- sylow_subgroup(p)[源代码]#
返回组的p-Sylow子组。
算法在中进行了描述 [1] ，第4章，第7节
实例
>>> from sympy.combinatorics.named_groups import DihedralGroup >>> from sympy.combinatorics.named_groups import SymmetricGroup >>> from sympy.combinatorics.named_groups import AlternatingGroup
>>> D = DihedralGroup(6) >>> S = D.sylow_subgroup(2) >>> S.order() 4 >>> G = SymmetricGroup(6) >>> S = G.sylow_subgroup(5) >>> S.order() 5
>>> G1 = AlternatingGroup(3) >>> G2 = AlternatingGroup(5) >>> G3 = AlternatingGroup(9)
>>> S1 = G1.sylow_subgroup(3) >>> S2 = G2.sylow_subgroup(3) >>> S3 = G3.sylow_subgroup(3)
>>> len1 = len(S1.lower_central_series()) >>> len2 = len(S2.lower_central_series()) >>> len3 = len(S3.lower_central_series())
>>> len1 == len2 True >>> len1 < len3 True
- property transitivity_degree#
计算群的传递度。
解释
A permutation group \(G\) acting on \(\Omega = \{0, 1, \dots, n-1\}\) is
k-fold transitive, if, for any \(k\) points \((a_1, a_2, \dots, a_k) \in \Omega\) and any \(k\) points \((b_1, b_2, \dots, b_k) \in \Omega\) there exists \(g \in G\) such that \(g(a_1) = b_1, g(a_2) = b_2, \dots, g(a_k) = b_k\) The degree of transitivity of \(G\) is the maximumksuch that \(G\) isk-fold transitive. ([8])实例
>>> from sympy.combinatorics import Permutation, PermutationGroup >>> a = Permutation([1, 2, 0]) >>> b = Permutation([1, 0, 2]) >>> G = PermutationGroup([a, b]) >>> G.transitivity_degree 3
参见