排列群¶

class sympy.combinatorics.perm_groups.PermutationGroup(*args, dups=True, **kwargs)[源代码][源代码]¶

定义置换群的类。

属性:

args: 返回 ‘self’ 的参数元组。
assumptions0: 返回对象 \(type\) 假设。
base: 返回 Schreier-Sims 算法中的一个基。
basic_orbits: 返回相对于基和强生成集的基本轨道。
basic_stabilizers: 返回相对于基和强生成集的稳定子链。
basic_transversals: 返回相对于基和强生成集的基本遍历。
canonical_variables: 返回一个字典，将 self.bound_symbols 中定义的任何变量映射到与表达式中任何自由符号不冲突的符号。
degree: 返回群中排列的大小。
elements: 返回置换群的所有元素作为一个列表
expr_free_symbols
free_symbols: 从自身的原子中返回那些自由符号。
func: 表达式中的顶级函数。
generators: 返回群的生成元。
identity: 返回置换群的单位元。
is_abelian: 测试群是否为阿贝尔群。
is_algebraic
is_alternating: 如果组是交替的，则返回 True。
is_antihermitian
is_commutative
is_comparable: 如果 self 可以计算为一个具有精度的实数（或已经是一个实数），则返回 True，否则返回 False。
is_complex
is_composite
is_cyclic: 如果该群是循环群，则返回 True。
is_dihedral: 如果该组是二面体，则返回 True。
is_even
is_extended_negative
is_extended_nonnegative
is_extended_nonpositive
is_extended_nonzero
is_extended_positive
is_extended_real
is_finite
is_hermitian
is_imaginary
is_infinite
is_integer
is_irrational
is_negative
is_nilpotent: 测试群是否为幂零群。
is_noninteger
is_nonnegative
is_nonpositive
is_nonzero
is_odd
is_perfect: 如果该组是完美的，则返回 True。
is_polar
is_polycyclic: 如果一个群是多循环的，则返回 True。
is_positive
is_prime
is_rational
is_real
is_solvable: 测试群组是否可解。
is_symmetric: 如果该组是对称的，则返回 True。
is_transcendental
is_trivial: 测试组是否为平凡组。
is_zero
max_div: 置换群阶的最大真因子。
strong_gens: 从 Schreier-Sims 算法返回一个强生成集。
transitivity_degree: 计算该群的传递度。

方法

`abelian_invariants`()	返回给定群的阿贝尔不变量。
`as_content_primitive`([radical, clear])	一个存根，允许在计算表达式的内容和基本组件时跳过基本参数（如元组）。
`as_dummy`()	返回表达式，其中任何具有结构绑定符号的对象都被替换为在其出现的对象中唯一的规范符号，并且仅对交换性具有默认假设为True。
`atoms`(*types)	返回构成当前对象的原子。
`baseswap`(base, strong_gens, pos[, ...])	在基和强生成集中交换两个连续的基点。
`center`()	返回置换群的中心。
`centralizer`(other)	返回一个群/集合/元素的中心化子。
`class_key`()	类的好顺序。
`commutator`(G, H)	返回两个子群的换位子群。
`compare`(other)	如果对象在规范意义上小于、等于或大于其他对象，则返回 -1、0、1。
`composition_series`()	返回一个群的合成列作为置换群的列表。
`conjugacy_class`(x)	返回群中元素的共轭类。
`conjugacy_classes`()	返回群的共轭类。
`contains`(g[, strict])	测试排列 `g` 是否属于自身，`G`。
`coset_factor`(g[, factor_index])	返回 G``（自身）的 ``g 的陪集分解
`coset_rank`(g)	使用 Schreier-Sims 表示进行排序。
`coset_table`(H)	返回自身在H中的标准（右）陪集表，作为列表的列表。
`coset_transversal`(H)	使用[1]中第4.6.7小节描述的第二种方法，返回由其子群H生成的self的右陪集的横向。
`coset_unrank`(rank[, af])	使用 Schreier-Sims 表示进行无序排列
`count`(query)	计算匹配的子表达式的数量。
`count_ops`([visual])	用于返回操作计数的 count_ops 的包装器。
`derived_series`()	返回该组的派生系列。
`derived_subgroup`()	计算导出子群。
`doit`(**hints)	评估默认情况下不评估的对象，如极限、积分、求和和乘积。
`dummy_eq`(other[, symbol])	比较两个表达式并处理哑符号。
`equals`(other)	如果由群中元素生成的置换群相同，即它们表示相同的置换群，则返回 `True`。
`find`(query[, group])	查找所有匹配查询的子表达式。
`fromiter`(args, **assumptions)	从可迭代对象创建一个新对象。
`generate`([method, af])	返回迭代器以生成组中的元素。
`generate_dimino`([af])	使用 Dimino 算法生成群元素。
`generate_schreier_sims`([af])	使用 Schreier-Sims 表示法按 coset_rank 顺序生成群元素
`generator_product`(g[, original])	返回一个强生成元列表 \([s1, \dots, sn]\)，使得 \(g = sn \times \dots \times s1\)。
`has`(*patterns)	测试是否有任何子表达式匹配任何模式。
`has_free`(*patterns)	如果 self 包含对象 `x` 作为自由表达式，则返回 True，否则返回 False。
`has_xfree`(s)	如果 self 有 s 中的任何一个模式作为自由参数，则返回 True，否则返回 False。
`index`(H)	返回置换群的索引。
`is_alt_sym`([eps, _random_prec])	对称/交替群的蒙特卡罗测试，适用于次数 >= 8。
`is_elementary`(p)	如果该群是初等阿贝尔群，则返回 `True`。
`is_normal`(gr[, strict])	测试 `G=self` 是否是 `gr` 的正规子群。
`is_primitive`([randomized])	测试一个群是否是原始的。
`is_same`(b[, approx])	如果 a 和 b 结构相同则返回 True，否则返回 False。
`is_subgroup`(G[, strict])	如果 `self` 的所有元素都属于 `G`，则返回 `True`。
`is_transitive`([strict])	测试组是否是传递的。
`lower_central_series`()	返回群的低中心列。
`make_perm`(n[, seed])	将 `n` 个从 pgroup 中随机选择的排列相乘，从单位排列开始。
`match`(pattern[, old])	模式匹配。
`matches`(expr[, repl_dict, old])	用于 match() 的辅助方法，用于在 self 中的通配符符号与 expr 中的表达式之间寻找匹配。
`minimal_block`(points)	对于一个传递群，找到由 `points` 生成的块系统。
`minimal_blocks`([randomized])	对于一个传递群，返回所有最小块系统的列表。
`normal_closure`(other[, k])	返回一个子群/置换集的正规闭包。
`orbit`(alpha[, action])	计算alpha的轨道 \(\{g(\alpha) \| g \in G\}\) 作为一个集合。
`orbit_rep`(alpha, beta[, schreier_vector])	返回一个将 `alpha` 发送到 `beta` 的组元素。
`orbit_transversal`(alpha[, pairs])	计算 `alpha` 轨道的一个横截面作为集合。
`orbits`([rep])	返回 `self` 的轨道，按照每个轨道中的最低元素排序。
`order`()	返回组的顺序：可以从组的元素生成的排列数。
`pointwise_stabilizer`(points[, incremental])	返回一组点的逐点稳定器。
`polycyclic_group`()	返回具有以下参数的 PolycyclicGroup 实例：
`presentation`([eliminate_gens])	返回群的 \(FpGroup\) 表示形式。
`random`([af])	返回一个随机群元素
`random_pr`([gen_count, iterations, _random_prec])	使用乘积替换返回一个随机群元素。
`random_stab`(alpha[, schreier_vector, ...])	从 `alpha` 的稳定器中随机选择的元素。
`rcall`(*args)	通过表达式树递归应用于参数。
`refine`([assumption])	请参阅 sympy.assumptions 中的 refine 函数。
`replace`(query, value[, map, simultaneous, exact])	将 `self` 中匹配的子表达式替换为 `value`。
`rewrite`(*args[, deep])	使用定义的规则重写 self。
`schreier_sims`()	Schreier-Sims 算法。
`schreier_sims_incremental`([base, gens, slp_dict])	将一系列点和生成集扩展为基和强生成集。
`schreier_sims_random`([base, gens, ...])	随机化 Schreier-Sims 算法。
`schreier_vector`(alpha)	计算 `alpha` 的 Schreier 向量。
`simplify`(**kwargs)	请参阅 sympy.simplify 中的 simplify 函数。
`sort_key`([order])	返回一个排序键。
`stabilizer`(alpha)	返回 `alpha` 的稳定子子群。
`strong_presentation`()	返回群的强有限表示。
`subgroup`(gens)	返回由 \(gens\) 生成的子群，\(gens\) 是群中元素的列表。
`subgroup_search`(prop[, base, strong_gens, ...])	找到所有满足属性 `prop` 的子群。
`subs`(args, *kwargs)	在简化参数后，在表达式中用新内容替换旧内容。
`sylow_subgroup`(p)	返回群的 p-Sylow 子群。
`xreplace`(rule)	替换表达式中对象的出现。

复制
could_extract_minus_sign
is_hypergeometric

参见

sympy.combinatorics.polyhedron.Polyhedron
sympy.combinatorics.permutations.Permutation

参考文献

[1]

Holt, D., Eick, B., O’Brien, E. “计算群论手册”

[2]

Seress, A. 《置换群算法》

[3]

https://zh.wikipedia.org/wiki/Schreier向量

[4]

https://zh.wikipedia.org/wiki/%E5%B0%BC%E7%88%BE%E6%A3%AE%E8%BD%89%E6%8F%9B#%E4%BA%A7%E5%93%81%E6%9B%BF%E6%8D%A2%E7%AE%97%E6%B3%95

[5]

Frank Celler, Charles R.Leedham-Green, Scott H.Murray, Alice C.Niemeyer, 和 E.A.O’Brien. “生成有限群的随机元素”

[6]

https://en.wikipedia.org/wiki/块_%28置换群理论%29

[7]

https://algorithmist.com/wiki/并查集

[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/中心化子和正规化子

[11]

https://groupprops.subwiki.org/wiki/导出子群

[12]

https://en.wikipedia.org/wiki/Nilpotent_group

[13]

https://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf

[14]

https://docs.gap-system.org/doc/ref/manual.pdf

示例

>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> from sympy.combinatorics import Polyhedron

对应于 \(2 imes 2\) 魔方的前、右和底面运动的排列被定义为：

>>> 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)

这些作为排列传递给 PermutationGroup：

>>> G = PermutationGroup(F, R, D)
>>> G.order()
3674160

该组可以提供给一个多面体，以便跟踪正在移动的对象。那里给出了一个涉及 \(2 imes 2\) 魔方的例子，但这里是一个简单的演示：

>>> 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)

或者可以将排列作为选定排列的乘积，并直接将其应用于可迭代对象：

>>> P10 = G.make_perm([0, 1])
>>> P10('ABC')
['C', 'A', 'B']

__contains__(i)[源代码][源代码]¶

如果 i 包含在 PermutationGroup 中，则返回 True。

示例

>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> p = Permutation(1, 2, 3)
>>> Permutation(3) in PermutationGroup(p)
True

__mul__(other)[源代码][源代码]¶

返回两个置换群的直积作为一个置换群。

示例

>>> 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

static __new__(

cls,

*args,

dups=True,

**kwargs,

)[源代码][源代码]¶: 默认构造函数。接受 Cycle 和 Permutation 形式。除非 dups 关键字为 False，否则会移除重复项。

__weakref__¶: 对象的弱引用列表（如果已定义）

_coset_representative(g, H)[源代码][源代码]¶: 返回由 self.coset_transversal(H) 计算的横截面中的 Hg 的代表。

classmethod _distinct_primes_lemma(primes)[源代码][源代码]¶: 测试是否只有一种阶数的循环群的子程序。

_eval_is_alt_sym_monte_carlo( eps=0.05, perms=None, )[源代码][源代码]¶

使用蒙特卡洛算法的测试。

参数:

epsfloat, 可选

False 返回值的错误标准。

权限list[排列], 可选

如果明确给出，它会在给定的测试候选者中进行测试。

如果 None ，它会随机计算 N_eps 并从组中选择 N_eps 个排列样本。

参见

_check_cycles_alt_sym

_eval_is_alt_sym_naive( only_sym=False, only_alt=False, )[源代码][源代码]¶: 使用群组阶的简单测试。

_p_elements_group(p)[源代码][源代码]¶: 对于一个阿贝尔 p-群，返回由所有阶为 p 的元素（以及单位元）组成的子群

_random_pr_init( r, n, _random_prec_n=None, )[源代码][源代码]¶

为产品替换算法初始化随机生成器。

参见

random_pr

注释

此函数有副作用：它改变了属性 self._random_gens

_sylow_alt_sym(p)[源代码][源代码]¶

返回对称群或交错群的一个 p-Sylow 子群。

参见

sylow_subgroup, is_alt_sym

_union_find_merge( first, second, ranks, parents, not_rep, )[源代码][源代码]¶

在并查集数据结构中合并两个类。

参见

minimal_block, _union_find_rep

注释

此函数有副作用：由于类合并，类代表列表 parents 、类大小列表 ranks 以及非代表元素列表 not_rep 会被更改。

参考文献

[1]

Holt, D., Eick, B., O’Brien, E. “计算群论手册”

[7]

https://algorithmist.com/wiki/并查集

_union_find_rep(num, parents)[源代码][源代码]¶

在并查集数据结构中查找类的代表。

参见

minimal_block, _union_find_merge

注释

此函数有副作用：由于路径压缩，类代表列表 parents 会被修改。

参考文献

[1]

Holt, D., Eick, B., O’Brien, E. “计算群论手册”

[7]

https://algorithmist.com/wiki/并查集

_verify(K, phi, z, alpha)[源代码][源代码]¶

返回生成器 gens`_h 中的关系子 rels 列表，这些关系子通过 phi 映射到 H.generators，使得给定 K 的有限表示 <gens_k | rels_k> 在 gens_h 的子集上 <gens_h | rels_k + rels> 是 H 的有限表示。

参见

strong_presentation, presentation, stabilizer

示例

>>> 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 同构于有限多个素数幂阶的非平凡循环群的直积。

注释

我们采用的约定是，平凡群的不变量为 []。

示例

>>> 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 算法中的一个基。

参见

strong_gens, basic_transversals, basic_orbits, basic_stabilizers

示例

>>> 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, )[源代码][源代码]¶

在基和强生成集中交换两个连续的基点。

参数:

基, 强生成元: 基本集和强生成集。
pos: 进行交换的位置。
随机化: 在随机版本和确定版本之间切换。
横截面: 基本轨道的横截面，如果已知。
基本轨道: 基本轨道，如果已知。
strong_gens_distr: 由基本稳定子分布的强生成元，如果已知的话。

返回:

(基, 强生成元): base 是新的基，而 strong_gens 是相对于它的生成集。

参见

schreier_sims

注释

该算法的确定性版本在 [1], pp. 102-103 中讨论；随机化版本在 [1], p.103 和 [2], p.98 中讨论。它属于拉斯维加斯类型。注意 [1] 在 BASESWAP 的伪代码和讨论中有一个错误：在伪代码的第3行，\(|\beta_{i+1}^{\left\langle T\right\rangle}|\) 应替换为 \(|\beta_{i}^{\left\langle T\right\rangle}|\)，算法讨论中也是如此。

示例

>>> 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

property basic_orbits¶

返回相对于基和强生成集的基本轨道。

参见

base, strong_gens, basic_transversals, basic_stabilizers

示例

>>> 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¶

返回相对于基和强生成集的稳定子链。

参见

base, strong_gens, basic_orbits, basic_transversals

示例

>>> 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¶

返回相对于基和强生成集的基本遍历。

参见

strong_gens, base, basic_orbits, basic_stabilizers

示例

>>> 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()[源代码][源代码]¶

返回置换群的中心。

参见

centralizer

注释

这是一个简单的实现，直接应用了 .centralizer()

示例

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> D = DihedralGroup(4)
>>> G = D.center()
>>> G.order()
2

centralizer(other)[源代码][源代码]¶

返回一个群/集合/元素的中心化子。

参数:

其他: 一个置换群/置换列表/单个置换

参见

subgroup_search

注释

该实现是使用 G 群的特定基对 .subgroup_search() 的应用。

示例

>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
... CyclicGroup)
>>> S = SymmetricGroup(6)
>>> C = CyclicGroup(6)
>>> H = S.centralizer(C)
>>> H.is_subgroup(C)
True

commutator(G, H)[源代码][源代码]¶

返回两个子群的换位子群。

参见

derived_subgroup

注释

两个子群 \(H, G\) 的换位子等于所有生成元的换位子的正规闭包，即对于 \(H\) 的生成元 \(h\) 和 \(G\) 的生成元 \(g\)，有 \(hgh^{-1}g^{-1}\) ([1], p.28)

示例

>>> from sympy.combinatorics.named_groups import (SymmetricGroup,
... AlternatingGroup)
>>> S = SymmetricGroup(5)
>>> A = AlternatingGroup(5)
>>> G = S.commutator(S, A)
>>> G.is_subgroup(A)
True

composition_series()[源代码][源代码]¶

返回一个群的合成列作为置换群的列表。

示例

>>> 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 中找到元素在共轭下的轨道来直接计算共轭类。该算法仅适用于相对小阶的置换群，但在这方面类似于 orbit() 函数本身。

示例

>>> from sympy.combinatorics import Permutation, SymmetricGroup
>>> S3 = SymmetricGroup(3)
>>> S3.conjugacy_class(Permutation(0, 1, 2))
{(0 1 2), (0 2 1)}

conjugacy_classes()[源代码][源代码]¶

返回群的共轭类。

示例

>>> 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。

参见

coset_factor, sympy.core.basic.Basic.has, __contains__

示例

>>> 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 的陪集分解

参见

sympy.combinatorics.util._strip

示例

>>> 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 表示进行排序。

参见

coset_factor

示例

>>> 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)

coset_table(H)[源代码][源代码]¶: 返回自身在H中的标准（右）陪集表，作为列表的列表。

coset_transversal(H)[源代码][源代码]¶: 使用[1]中第4.6.7小节描述的第二种方法，返回由其子群H生成的self的右陪集的横向。

coset_unrank(rank, af=False)[源代码][源代码]¶

使用 Schreier-Sims 表示进行无序排列

如果 0 <= rank < order，coset_unrank 是 coset_rank 的逆操作；否则它返回 None。

property degree¶

返回群中排列的大小。

参见

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\)。

参见

derived_subgroup

示例

>>> 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()[源代码][源代码]¶

计算导出子群。

参见

derived_series

示例

>>> 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
[(3), (3)(1 2), (1 3), (2 3), (1 2 3), (1 3 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, )[源代码][源代码]¶

返回迭代器以生成组中的元素。

示例

>>> 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 ，它将生成排列的数组形式。

参考文献

[1]

计算机代数系统中置换群的各种算法的实现：AXIOM，N.J. Doye，硕士论文

示例

>>> 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]]

generate_schreier_sims(af=False)[源代码][源代码]¶

使用 Schreier-Sims 表示法按 coset_rank 顺序生成群元素

如果 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, )[源代码][源代码]¶: 返回一个强生成元列表 \([s1, \dots, sn]\)，使得 \(g = sn \times \dots \times s1\)。如果 original=True，则列表仅包含原始群生成元。

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。

参见

_check_cycles_alt_sym

注释

该算法本身使用了群论和数论中的一些非平凡结果：1) 如果一个度为 n 的传递群 G 包含一个长度为 n/2 < p < n-2 的循环，其中 p 是素数，那么 G 是对称群或交错群（[1], pp. 81-82）2) 在对称/交错群中具有第1点所述性质的元素的比例大约为 \(\log(2)/\log(n)`（[1], p.82; [2], pp. 226-227）。辅助函数 ``_check_cycles_alt_sym`\) 用于遍历排列中的循环，并寻找满足第1点的循环。

示例

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> D = DihedralGroup(10)
>>> D.is_alt_sym()
False

property is_alternating¶

如果组是交替的，则返回 True。

参见

is_alt_sym

注释

这使用了一个涉及计算完整群阶的简单测试。如果你需要对大型群进行更快速的分类，可以使用 PermutationGroup.is_alt_sym()。然而，PermutationGroup.is_alt_sym() 可能不准确，并且无法区分交错群和对称群。

示例

>>> 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

property is_cyclic¶

如果该群是循环群，则返回 True。

注释

如果一个群 \(n\) 的阶可以分解为互异的素数 \(p_1, p_2, \dots , p_s\)，并且如果

\[\forall i, j \in \{1, 2, \dots, s \}:\n p_i \not \equiv 1 \pmod {p_j}\]

成立，则阶为 \(n\) 的群只有一个，即循环群 [1]。这是关于阶为 \(15, 35, \dots\) 的群是循环群的引理的推广。

此外，如果已经找到群的阶，这些附加的引理可以用来测试一个群是否是循环的。

如果群是阿贝尔群且群的阶是平方自由的，那么该群是循环群。
如果群的阶小于 \(6\) 且不等于 \(4\)，则该群是循环群。
如果群的阶是素数，那么这个群是循环群。

参考文献

[1]

1978年：约翰·S·罗斯：《群论课程》，《有限群论导论》：1.4

示例

>>> from sympy.combinatorics.named_groups import AbelianGroup
>>> G = AbelianGroup(3, 4)
>>> G.is_cyclic
True
>>> G = AbelianGroup(4, 4)
>>> G.is_cyclic
False

property is_dihedral¶

如果该组是二面体，则返回 True。

参考文献

[Di1]

https://math.stackexchange.com/questions/827230/given-a-cayley-table-is-there-an-algorithm-to-determine-if-it-is-a-dihedral-gro/827273#827273

[Di2]

https://kconrad.math.uconn.edu/blurbs/grouptheory/dihedral.pdf

[Di3]

https://kconrad.math.uconn.edu/blurbs/grouptheory/dihedral2.pdf

[Di4]

https://zh.wikipedia.org/wiki/二面体群

示例

>>> 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

is_elementary(p)[源代码][源代码]¶

如果该群是初等阿贝尔群，则返回 True。初等阿贝尔群是一个有限阿贝尔群，其中每个非平凡元素的阶为 \(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¶

测试群是否为幂零群。

参见

lower_central_series, is_solvable

示例

>>> 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 的正规子群。

示例

>>> 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)[源代码][源代码]¶

测试一个群是否是原始的。

参见

minimal_block, random_stab

注释

该算法在 [1] 的第 83 页中描述，并使用函数 minimal_block 来搜索形式为 \(\{0, k\}\) 的块，其中 k 遍历 \(G_0\) 的轨道代表，\(G_0\) 是 0 的稳定子。该算法的复杂度为 \(O(n^2)\)，其中 n 是群的阶数，如果 \(G_0\) 很小，则性能会很差。

提供了两种实现方式：一种使用函数 stabilizer 确定性地找到 \(G_0\)，另一种（默认）使用 random_stab 生成 \(G_0\) 的随机元素，希望它们能生成一个 \(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], p.29)。

参见

is_nilpotent, derived_series

示例

>>> from sympy.combinatorics.named_groups import SymmetricGroup
>>> S = SymmetricGroup(3)
>>> S.is_solvable
True

is_subgroup(G, strict=True)[源代码][源代码]¶

如果 self 的所有元素都属于 G，则返回 True。

如果 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。

参见

is_alt_sym

注释

示例

>>> 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

is_transitive(strict=True)[源代码][源代码]¶

测试组是否是传递的。

示例

>>> 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], p.29）。

返回:

排列群列表，顺序为 \(G = G_0, G_1, G_2, \ldots\)

参见

commutator, derived_series

示例

>>> 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)[源代码][源代码]¶

将 pgroup 中的 n 个随机选择的排列相乘，从恒等排列开始。如果 n 是一个整数列表，这些整数将被用来选择排列，并且它们将按从左到右的顺序应用：make_perm((A, B, C)) 将给出 CBA(I)，其中 I 是恒等排列。

seed 用于为从 pgroup 中随机选择排列设置种子。如果这是一个整数列表，则将按给定顺序选择 pgroup 中对应的排列。这主要用于测试目的。

参见

random

示例

>>> 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¶

置换群阶的最大真因子。

参见

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 生成的块系统。

参见

_union_find_rep, _union_find_merge, is_transitive, is_primitive

示例

>>> 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\)。

参见

minimal_block, is_transitive, is_primitive

示例

>>> 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)[源代码][源代码]¶

返回一个子群/置换集的正规闭包。

参数:

其他: 子组/排列列表/单个排列
k: 一个特定实现的参数，用于确定一次连接到 other 的共轭数量

参见

commutator, derived_subgroup, random_pr

注释

该算法在 [1] 的第 73-74 页中描述；它利用了通过乘积替换算法生成的置换群的随机元素。

示例

>>> 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

orbit(alpha, action='tuples')[源代码][源代码]¶

计算alpha的轨道 \(\{g(\alpha) | g \in G\}\) 作为一个集合。

参见

orbit_transversal

示例

>>> 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 的组元素。

参见

schreier_vector

示例

>>> 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 轨道的一个横截面作为集合。

参见

orbit

示例

>>> 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 给出。

参见

degree

示例

>>> 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, )[源代码][源代码]¶

返回一组点的逐点稳定器。

参见

stabilizer, schreier_sims_incremental

注释

当 incremental == True 时，不是使用连续调用 .stabilizer() 的明显实现，而是使用增量 Schreier-Sims 算法来获取一个以给定点为起始段的基。

示例

>>> 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

polycyclic_group()[源代码][源代码]¶: 返回具有以下参数的 PolycyclicGroup 实例：

presentation(eliminate_gens=True)[源代码][源代码]¶

返回群的 \(FpGroup\) 表示形式。

该算法在 [1] 的第 6.1 章节中描述。

random(af=False)[源代码][源代码]¶: 返回一个随机群元素

random_pr( gen_count=11, iterations=50, _random_prec=None, )[源代码][源代码]¶

使用乘积替换返回一个随机群元素。

参见

_random_pr_init

random_stab( alpha, schreier_vector=None, _random_prec=None, )[源代码][源代码]¶

从 alpha 的稳定器中随机选择的元素。

alpha 的 Schreier 向量是一个可选参数，用于加速重复调用。该算法在 [1]，第81页中描述。

参见

random_pr, orbit_rep

schreier_sims()[源代码][源代码]¶

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, )[源代码][源代码]¶

将一系列点和生成集扩展为基和强生成集。

参数:

基础: 要扩展到基点的点序列。可选参数，默认值为 []。
生成: 生成集将被扩展为相对于所获得基的强生成集。可选参数，默认值为 self.generators。
slp_dict: 如果 \(True\)，返回一个字典 \({g: gens}\)，其中 \(g\) 是每个强生成元，\(gens\) 是在 \(strong_gens\) 中位于 \(g\) 之前的强生成元列表，使得 \(gens\) 中元素的乘积等于 \(g\)。

返回:

(基, 强生成元): base 是所得到的基础，而 strong_gens 是相对于它的强生成集。原始参数 base、gens 保持不变。

参见

schreier_sims, schreier_sims_random

注释

这个版本的 Schreier-Sims 算法在多项式时间内运行。实现中有一些假设——如果提供了平凡群，base 和 gens 会立即返回，因为任何点的序列都是平凡群的基。如果恒等元存在于生成器 gens 中，它将被移除，因为它是一个冗余生成器。实现描述见 [1]，第 90-93 页。

示例

>>> 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_random( base=None, gens=None, consec_succ=10, _random_prec=None, )[源代码][源代码]¶

随机化 Schreier-Sims 算法。

参数:

基础: 要扩展到基数的序列。
生成: 生成集将被扩展为强生成集。
consec_succ: 定义错误答案概率的参数。
_random_prec: 用于测试目的的内部参数。

返回:

(基, 强生成元): base 是基础，而 strong_gens 是相对于它的强生成集。

参见

schreier_sims

注释

该算法在[1]的第97-98页有详细描述。它将轨道``orbs``和置换群``stabs``扩展为基本轨道和基本稳定器，以生成最终的基和强生成集。扩展过程的思想是通过稳定器链“筛选”随机群元素，并在筛选不成功时沿路径修正稳定器/轨道。辅助函数``_strip``用于尝试根据当前稳定器链的状态分解随机群元素，并报告元素是否完全分解（成功筛选）或未完全分解（不成功筛选）。在后一种情况下，报告筛选失败的层级，并相应地修正``stabs``、base、gens``和``orbs。终止条件是``consec_succ``次连续成功筛选通过。这确保了当前的``base``和``gens``至少以`1 - 1/text{consec_succ}`的概率形成一个BSGS。

示例

>>> 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

schreier_vector(alpha)[源代码][源代码]¶

计算 alpha 的 Schreier 向量。

参见

orbit

示例

>>> 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 的稳定子子群。

参见

orbit

示例

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> G = DihedralGroup(6)
>>> G.stabilizer(5)
PermutationGroup([
    (5)(0 4)(1 3)])

property strong_gens¶

从 Schreier-Sims 算法返回一个强生成集。

参见

base, basic_transversals, basic_orbits, basic_stabilizers

示例

>>> 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()[源代码][源代码]¶

返回一个群的强有限表示。返回的群的生成元与群的强生成元顺序相同。

该算法基于 Sims 的 Verify 算法，描述在 [1] 的第 6 章。

参见

presentation, _verify

示例

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> P = DihedralGroup(4)
>>> G = P.strong_presentation()
>>> P.order() == G.order()
True

subgroup(gens)[源代码][源代码]¶: 返回由 \(gens\) 生成的子群，\(gens\) 是群中元素的列表。

subgroup_search( prop, base=None, strong_gens=None, tests=None, init_subgroup=None, )[源代码][源代码]¶

找到所有满足属性 prop 的子群。

参数:

属性: 要使用的属性。必须在组元素上调用，并且总是返回 True 或 False。假设所有满足 prop 的组元素确实形成了一个子组。
基础: 超群的基础。
strong_gens: 超群的一个强生成集。
测试: 一个长度等于 base 长度的可调用对象列表。这些用于通过部分基图像排除组元素，因此如果元素 g 已知不满足基于 g 发送的前 l + 1 个基点的 prop 基，则 tests[l](g) 返回 False。
init_subgroup: 如果已知所寻求的组的一个子组，可以将其作为此参数传递给函数。

返回:

res: 所有满足 prop 的元素的子群。该群的生成集保证相对于基 base 是一个强生成集。

注释

这个函数非常冗长且复杂，需要一些仔细的关注。其实现描述在 [1]，第 114-117 页，这里的代码注释遵循书中伪代码的行文以确保清晰。

一般来说，复杂度是指数级的，因为搜索过程本身会访问超群的所有成员。然而，有很多测试用于修剪搜索树，用户可以通过 tests 参数定义自己的测试，因此在实践中，对于某些计算来说，情况并不糟糕。

过程的关键部分是频繁执行的基底变换（这是伪代码中的第11行），以便获得一个新的基本稳定子。书中提到这可以通过使用 .baseswap(...) 来完成，然而当前的实现使用了一种更直接的方法来找到下一个基本稳定子——在前一个基本稳定子上调用函数 .stabilizer(...)。

示例

>>> 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

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¶

计算该群的传递度。

参见

is_transitive, orbit

示例

>>> from sympy.combinatorics import Permutation, PermutationGroup
>>> a = Permutation([1, 2, 0])
>>> b = Permutation([1, 0, 2])
>>> G = PermutationGroup([a, b])
>>> G.transitivity_degree
3