公用事业#
- sympy.combinatorics.util._base_ordering(base, degree)[源代码]#
Order \(\{0, 1, \dots, n-1\}\) so that base points come first and in order.
- 参数:
base : the base
degree : the degree of the associated permutation group
- 返回:
一览表
base_ordering这样的话base_ordering[point]是数
point在订单中。
实例
>>> 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]
笔记
This is used in backtrack searches, when we define a relation \(\ll\) on the underlying set for a permutation group of degree \(n\), \(\{0, 1, \dots, n-1\}\), so that if \((b_1, b_2, \dots, b_k)\) is a base we have \(b_i \ll b_j\) whenever \(i<j\) and \(b_i \ll a\) for all \(i\in\{1,2, \dots, k\}\) and \(a\) is not in the base. The idea is developed and applied to backtracking algorithms in [1], pp.108-132. The points that are not in the base are taken in increasing order.
工具书类
[R95]Holt，D.，Eick，B.，O'Brien，E.《计算群理论手册》
- sympy.combinatorics.util._check_cycles_alt_sym(perm)[源代码]#
用n/2<p<n-2检查素数长度p的周期。
解释
在这里 \(n\) 是排列的程度。这是一个辅助函数，因为函数是从组合数学。perm_群.
实例
>>> 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 : a sequence of points in \(\{0, 1, \dots, n-1\}\)
gens : a list of elements of a permutation group of degree \(n\).
- 返回:
列表
List of length \(k\), where \(k\) is the length of base. The \(i\)-th entry contains those elements in gens which fix the first \(i\) elements of base (so that the \(0\)-th entry is equal to gens itself). If no element fixes the first \(i\) elements of base, the \(i\)-th element is set to a list containing the identity element.
解释
Notice that for a base \((b_1, b_2, \dots, b_k)\), the basic stabilizers are defined as \(G^{(i)} = G_{b_1, \dots, b_{i-1}}\) for \(i \in\{1, 2, \dots, k\}\).
实例
>>> 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相关结构。
- 参数:
base : the base
strong_gens : the strong generators
transversals : basic transversals
basic_orbits : basic orbits
strong_gens_distr : strong generators distributed by membership in basic stabilizers
- 返回:
(transversals, basic_orbits, strong_gens_distr)
where transversals are the basic transversals, basic_orbits are the basic orbits, and strong_gens_distr are the strong generators distributed by membership in basic stabilizers.
解释
必须提供基础和强发电机组；如果没有提供任何横截面、基本轨道或分布式强发生器，则从基础和强发电机组开始计算。
实例
>>> 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)[源代码]#
从基和强生成集计算基本轨道和断面。
- 参数:
base : The base.
strong_gens_distr : Strong generators distributed by membership in basic stabilizers.
transversals_only : bool, default: False
A flag switching between returning only the transversals and both orbits and transversals.
slp : bool, default: False
If
True, return a list of dictionaries containing the generator presentations of the elements of the transversals, i.e. the list of indices of generators fromstrong_gens_distr[i]such that their product is the relevant transversal element.
解释
发电机分布在基本稳定器上。如果可选参数
transversals_only设置为True，则只返回断面。实例
>>> 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)[源代码]#
从强大的发电机组中移除多余的发电机。
- 参数:
base : a base
strong_gens : a strong generating set relative to base
basic_orbits : basic orbits
strong_gens_distr : strong generators distributed by membership in basic stabilizers
- 返回:
关于
base它是strong_gens.
实例
>>> 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
笔记
中概述了此过程 [1] ，第95页。
工具书类
[R96]Holt，D.，Eick，B.，O'Brien，E.《计算群理论手册》
- sympy.combinatorics.util._strip(g, base, orbits, transversals)[源代码]#
尝试使用（可能是部分的）BSGS结构分解置换。
- 参数:
g : permutation to be decomposed
base : sequence of points
orbits : list
A list in which the
i-th entry is an orbit ofbase[i]under some subgroup of the pointwise stabilizer of ` \(base[0], base[1], ..., base[i - 1]`\). The groups themselves are implicit in this function since the only information we need is encoded in the orbits and transversalstransversals : list
A list of orbit transversals associated with the orbits orbits.
解释
这是通过处理序列来完成的
base作为一个实际的基地，轨道orbits和横截面transversals作为它的基本轨道和横截面。This process is called "sifting". A sift is unsuccessful when a certain orbit element is not found or when after the sift the decomposition does not end with the identity element.
争论
transversals是为轨道提供横向元素的字典列表orbits.实例
>>> 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)
笔记
算法在中进行了描述 [1] ，第89-90页。返回被分解元素的当前状态和筛选结束的级别的原因是它们为Schreier-Sims算法的随机版本提供了重要信息。
参见
sympy.combinatorics.perm_groups.PermutationGroup.schreier_sims,sympy.combinatorics.perm_groups.PermutationGroup.schreier_sims_random工具书类
[R97]Holt, D., Eick, B., O'Brien, E."Handbook of computational group theory"
- sympy.combinatorics.util._strong_gens_from_distr(strong_gens_distr)[源代码]#
从基本稳定器的发电机中回收强发电机组。
这只是第一个和第二个基本稳定器的发电机的结合。
- 参数:
strong_gens_distr : strong generators distributed by membership in basic stabilizers
实例
>>> 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)]