实用工具

sympy.combinatorics.util._base_ordering(base, degree)

将 \(\{0, 1, \dots, n-1\}\) 排序，使得基点优先且按顺序排列。

参数:

基础基础

度相关置换群的度数

返回:

一个列表 base_ordering 使得 base_ordering[point] 是

排序中的 point 数量。

注释

这在回溯搜索中使用，当我们为置换群的底层集合定义一个关系 \(\ll\)，其度数为 \(n\)，集合为 \(\{0, 1, \dots, n-1\}\)，使得如果 \((b_1, b_2, \dots, b_k)\) 是一个基，我们有 \(b_i \ll b_j\) 当且仅当 \(i<j\) 并且对于所有 \(i\in\{1,2, \dots, k\}\) 和不在基中的 \(a\)，有 \(b_i \ll a\)。这个想法在 [1] 中得到了发展和应用，见 pp.108-132。不在基中的点按递增顺序排列。

参考文献

[1]

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

示例

>>> from sympy.combinatorics import SymmetricGroup
>>> from sympy.combinatorics.util import _base_ordering
>>> S = SymmetricGroup(4)
>>> S.schreier_sims()
>>> _base_ordering(S.base, S.degree)
[0, 1, 2, 3]

sympy.combinatorics.util._check_cycles_alt_sym(perm)

检查长度为 p 的素数循环，其中 n/2 < p < n-2。

参见

sympy.combinatorics.perm_groups.PermutationGroup.is_alt_sym

示例

>>> from sympy.combinatorics.util import _check_cycles_alt_sym
>>> from sympy.combinatorics import Permutation
>>> a = Permutation([[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], [11, 12]])
>>> _check_cycles_alt_sym(a)
False
>>> b = Permutation([[0, 1, 2, 3, 4, 5, 6], [7, 8, 9, 10]])
>>> _check_cycles_alt_sym(b)
True

sympy.combinatorics.util._distribute_gens_by_base(base, gens)

根据基本稳定器中的成员资格分配组元素 gens。

参数:

base : \(\{0, 1, \dots, n-1\}\) 中的一系列点一系列点

gens : 一个置换群的元素列表，其阶数为 \(n\)。置换群的阶的元素列表

返回:

列表

长度为 \(k\) 的列表，其中 \(k\) 是 base 的长度。第 \(i\) 个条目包含那些在 gens 中固定了 base 前 \(i\) 个元素的元素（因此第 \(0\) 个条目等于 gens 本身）。如果没有元素固定 base 的前 \(i\) 个元素，则第 \(i\) 个元素设置为包含单位元素的列表。

参见

_strong_gens_from_distr, _orbits_transversals_from_bsgs

_handle_precomputed_bsgs

示例

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> from sympy.combinatorics.util import _distribute_gens_by_base
>>> D = DihedralGroup(3)
>>> D.schreier_sims()
>>> D.strong_gens
[(0 1 2), (0 2), (1 2)]
>>> D.base
[0, 1]
>>> _distribute_gens_by_base(D.base, D.strong_gens)
[[(0 1 2), (0 2), (1 2)],
 [(1 2)]]

sympy.combinatorics.util._handle_precomputed_bsgs(

base,

strong_gens,

transversals=None,

basic_orbits=None,

strong_gens_distr=None,

)

从现有的结构中计算BSGS相关的结构。

参数:

基础基础

strong_gens强生成元

横截面基本遍历

基本轨道基本轨道

strong_gens_distr由基本稳定子群成员资格分发的强生成器

返回:

(transversals, basic_orbits, strong_gens_distr)

其中 transversals 是基本横截面，basic_orbits 是基本轨道，而 strong_gens_distr 是按基本稳定子成员资格分布的强生成元。

参见

_orbits_transversals_from_bsgs, _distribute_gens_by_base

示例

>>> from sympy.combinatorics.named_groups import DihedralGroup
>>> from sympy.combinatorics.util import _handle_precomputed_bsgs
>>> D = DihedralGroup(3)
>>> D.schreier_sims()
>>> _handle_precomputed_bsgs(D.base, D.strong_gens,
... basic_orbits=D.basic_orbits)
([{0: (2), 1: (0 1 2), 2: (0 2)}, {1: (2), 2: (1 2)}], [[0, 1, 2], [1, 2]], [[(0 1 2), (0 2), (1 2)], [(1 2)]])

sympy.combinatorics.util._orbits_transversals_from_bsgs(

base,

strong_gens_distr,

transversals_only=False,

slp=False,

)

从基和强生成集计算基本轨道和横向。

参数:

基础基础。

strong_gens_distr由基本稳定子群成员资格分布的强生成元。

仅横切bool, 默认值: False

一个在仅返回横向和同时返回轨道和横向之间切换的标志。

slpbool, 默认值: False

如果 True ，返回一个字典列表，其中包含横截面元素的生成器表示，即来自 strong_gens_distr[i] 的生成器索引列表，使得它们的乘积是相关的横截面元素。

参见

_distribute_gens_by_base, _handle_precomputed_bsgs

示例

>>> from sympy.combinatorics import SymmetricGroup
>>> from sympy.combinatorics.util import _distribute_gens_by_base
>>> S = SymmetricGroup(3)
>>> S.schreier_sims()
>>> strong_gens_distr = _distribute_gens_by_base(S.base, S.strong_gens)
>>> (S.base, strong_gens_distr)
([0, 1], [[(0 1 2), (2)(0 1), (1 2)], [(1 2)]])

sympy.combinatorics.util._remove_gens(

base,

strong_gens,

basic_orbits=None,

strong_gens_distr=None,

)

从强生成集中移除冗余生成元。

参数:

基础一个基础

strong_gens : 相对于 base 的一个强生成集相对于的强生成集

基本轨道基本轨道

strong_gens_distr由基本稳定子群成员资格分发的强生成器

返回:

相对于 base 的一个强生成集，它是的子集

strong_gens.

注释

该程序在 [1]，第95页中概述。

参考文献

[1]

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

示例

>>> from sympy.combinatorics import SymmetricGroup
>>> from sympy.combinatorics.util import _remove_gens
>>> from sympy.combinatorics.testutil import _verify_bsgs
>>> S = SymmetricGroup(15)
>>> base, strong_gens = S.schreier_sims_incremental()
>>> new_gens = _remove_gens(base, strong_gens)
>>> len(new_gens)
14
>>> _verify_bsgs(S, base, new_gens)
True

sympy.combinatorics.util._strip(g, base, orbits, transversals)

尝试使用（可能是部分的）BSGS 结构来分解一个排列。

参数:

g待分解的排列

基础点的序列

轨道列表

一个列表，其中第 i 个条目是 base[i] 在某个子群下的轨道，该子群是 ` \(base[0], base[1], ..., base[i - 1]`\) 的逐点稳定子群。由于我们只需要的信息已经编码在轨道和横截面中，因此这些群本身在这个函数中是隐含的。

横截面列表

与轨道 orbits 相关联的轨道横向列表。

参见

sympy.combinatorics.perm_groups.PermutationGroup.schreier_sims

sympy.combinatorics.perm_groups.PermutationGroup.schreier_sims_random

注释

该算法在 [1]，第89-90页中描述。返回正在分解的元素的当前状态和筛选结束的级别的原因是，它们为Schreier-Sims算法的随机化版本提供了重要信息。

参考文献

[1]

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

示例

>>> from sympy.combinatorics import Permutation, SymmetricGroup
>>> from sympy.combinatorics.util import _strip
>>> S = SymmetricGroup(5)
>>> S.schreier_sims()
>>> g = Permutation([0, 2, 3, 1, 4])
>>> _strip(g, S.base, S.basic_orbits, S.basic_transversals)
((4), 5)

sympy.combinatorics.util._strong_gens_from_distr(strong_gens_distr)

从基本稳定器的生成元中检索强生成集。

这只是第一个和第二个基本稳定器生成器的并集。

参数:

strong_gens_distr由基本稳定子群成员资格分发的强生成器

参见

_distribute_gens_by_base

示例

>>> from sympy.combinatorics import SymmetricGroup
>>> from sympy.combinatorics.util import (_strong_gens_from_distr,
... _distribute_gens_by_base)
>>> S = SymmetricGroup(3)
>>> S.schreier_sims()
>>> S.strong_gens
[(0 1 2), (2)(0 1), (1 2)]
>>> strong_gens_distr = _distribute_gens_by_base(S.base, S.strong_gens)
>>> _strong_gens_from_distr(strong_gens_distr)
[(0 1 2), (2)(0 1), (1 2)]