Spaces:
Sleeping
Sleeping
| from sympy.combinatorics import Permutation | |
| from sympy.combinatorics.util import _distribute_gens_by_base | |
| rmul = Permutation.rmul | |
| def _cmp_perm_lists(first, second): | |
| """ | |
| Compare two lists of permutations as sets. | |
| Explanation | |
| =========== | |
| This is used for testing purposes. Since the array form of a | |
| permutation is currently a list, Permutation is not hashable | |
| and cannot be put into a set. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.permutations import Permutation | |
| >>> from sympy.combinatorics.testutil import _cmp_perm_lists | |
| >>> a = Permutation([0, 2, 3, 4, 1]) | |
| >>> b = Permutation([1, 2, 0, 4, 3]) | |
| >>> c = Permutation([3, 4, 0, 1, 2]) | |
| >>> ls1 = [a, b, c] | |
| >>> ls2 = [b, c, a] | |
| >>> _cmp_perm_lists(ls1, ls2) | |
| True | |
| """ | |
| return {tuple(a) for a in first} == \ | |
| {tuple(a) for a in second} | |
| def _naive_list_centralizer(self, other, af=False): | |
| from sympy.combinatorics.perm_groups import PermutationGroup | |
| """ | |
| Return a list of elements for the centralizer of a subgroup/set/element. | |
| Explanation | |
| =========== | |
| This is a brute force implementation that goes over all elements of the | |
| group and checks for membership in the centralizer. It is used to | |
| test ``.centralizer()`` from ``sympy.combinatorics.perm_groups``. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.testutil import _naive_list_centralizer | |
| >>> from sympy.combinatorics.named_groups import DihedralGroup | |
| >>> D = DihedralGroup(4) | |
| >>> _naive_list_centralizer(D, D) | |
| [Permutation([0, 1, 2, 3]), Permutation([2, 3, 0, 1])] | |
| See Also | |
| ======== | |
| sympy.combinatorics.perm_groups.centralizer | |
| """ | |
| from sympy.combinatorics.permutations import _af_commutes_with | |
| if hasattr(other, 'generators'): | |
| elements = list(self.generate_dimino(af=True)) | |
| gens = [x._array_form for x in other.generators] | |
| commutes_with_gens = lambda x: all(_af_commutes_with(x, gen) for gen in gens) | |
| centralizer_list = [] | |
| if not af: | |
| for element in elements: | |
| if commutes_with_gens(element): | |
| centralizer_list.append(Permutation._af_new(element)) | |
| else: | |
| for element in elements: | |
| if commutes_with_gens(element): | |
| centralizer_list.append(element) | |
| return centralizer_list | |
| elif hasattr(other, 'getitem'): | |
| return _naive_list_centralizer(self, PermutationGroup(other), af) | |
| elif hasattr(other, 'array_form'): | |
| return _naive_list_centralizer(self, PermutationGroup([other]), af) | |
| def _verify_bsgs(group, base, gens): | |
| """ | |
| Verify the correctness of a base and strong generating set. | |
| Explanation | |
| =========== | |
| This is a naive implementation using the definition of a base and a strong | |
| generating set relative to it. There are other procedures for | |
| verifying a base and strong generating set, but this one will | |
| serve for more robust testing. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.named_groups import AlternatingGroup | |
| >>> from sympy.combinatorics.testutil import _verify_bsgs | |
| >>> A = AlternatingGroup(4) | |
| >>> A.schreier_sims() | |
| >>> _verify_bsgs(A, A.base, A.strong_gens) | |
| True | |
| See Also | |
| ======== | |
| sympy.combinatorics.perm_groups.PermutationGroup.schreier_sims | |
| """ | |
| from sympy.combinatorics.perm_groups import PermutationGroup | |
| strong_gens_distr = _distribute_gens_by_base(base, gens) | |
| current_stabilizer = group | |
| for i in range(len(base)): | |
| candidate = PermutationGroup(strong_gens_distr[i]) | |
| if current_stabilizer.order() != candidate.order(): | |
| return False | |
| current_stabilizer = current_stabilizer.stabilizer(base[i]) | |
| if current_stabilizer.order() != 1: | |
| return False | |
| return True | |
| def _verify_centralizer(group, arg, centr=None): | |
| """ | |
| Verify the centralizer of a group/set/element inside another group. | |
| This is used for testing ``.centralizer()`` from | |
| ``sympy.combinatorics.perm_groups`` | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.named_groups import (SymmetricGroup, | |
| ... AlternatingGroup) | |
| >>> from sympy.combinatorics.perm_groups import PermutationGroup | |
| >>> from sympy.combinatorics.permutations import Permutation | |
| >>> from sympy.combinatorics.testutil import _verify_centralizer | |
| >>> S = SymmetricGroup(5) | |
| >>> A = AlternatingGroup(5) | |
| >>> centr = PermutationGroup([Permutation([0, 1, 2, 3, 4])]) | |
| >>> _verify_centralizer(S, A, centr) | |
| True | |
| See Also | |
| ======== | |
| _naive_list_centralizer, | |
| sympy.combinatorics.perm_groups.PermutationGroup.centralizer, | |
| _cmp_perm_lists | |
| """ | |
| if centr is None: | |
| centr = group.centralizer(arg) | |
| centr_list = list(centr.generate_dimino(af=True)) | |
| centr_list_naive = _naive_list_centralizer(group, arg, af=True) | |
| return _cmp_perm_lists(centr_list, centr_list_naive) | |
| def _verify_normal_closure(group, arg, closure=None): | |
| from sympy.combinatorics.perm_groups import PermutationGroup | |
| """ | |
| Verify the normal closure of a subgroup/subset/element in a group. | |
| This is used to test | |
| sympy.combinatorics.perm_groups.PermutationGroup.normal_closure | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.named_groups import (SymmetricGroup, | |
| ... AlternatingGroup) | |
| >>> from sympy.combinatorics.testutil import _verify_normal_closure | |
| >>> S = SymmetricGroup(3) | |
| >>> A = AlternatingGroup(3) | |
| >>> _verify_normal_closure(S, A, closure=A) | |
| True | |
| See Also | |
| ======== | |
| sympy.combinatorics.perm_groups.PermutationGroup.normal_closure | |
| """ | |
| if closure is None: | |
| closure = group.normal_closure(arg) | |
| conjugates = set() | |
| if hasattr(arg, 'generators'): | |
| subgr_gens = arg.generators | |
| elif hasattr(arg, '__getitem__'): | |
| subgr_gens = arg | |
| elif hasattr(arg, 'array_form'): | |
| subgr_gens = [arg] | |
| for el in group.generate_dimino(): | |
| conjugates.update(gen ^ el for gen in subgr_gens) | |
| naive_closure = PermutationGroup(list(conjugates)) | |
| return closure.is_subgroup(naive_closure) | |
| def canonicalize_naive(g, dummies, sym, *v): | |
| """ | |
| Canonicalize tensor formed by tensors of the different types. | |
| Explanation | |
| =========== | |
| sym_i symmetry under exchange of two component tensors of type `i` | |
| None no symmetry | |
| 0 commuting | |
| 1 anticommuting | |
| Parameters | |
| ========== | |
| g : Permutation representing the tensor. | |
| dummies : List of dummy indices. | |
| msym : Symmetry of the metric. | |
| v : A list of (base_i, gens_i, n_i, sym_i) for tensors of type `i`. | |
| base_i, gens_i BSGS for tensors of this type | |
| n_i number of tensors of type `i` | |
| Returns | |
| ======= | |
| Returns 0 if the tensor is zero, else returns the array form of | |
| the permutation representing the canonical form of the tensor. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.testutil import canonicalize_naive | |
| >>> from sympy.combinatorics.tensor_can import get_symmetric_group_sgs | |
| >>> from sympy.combinatorics import Permutation | |
| >>> g = Permutation([1, 3, 2, 0, 4, 5]) | |
| >>> base2, gens2 = get_symmetric_group_sgs(2) | |
| >>> canonicalize_naive(g, [2, 3], 0, (base2, gens2, 2, 0)) | |
| [0, 2, 1, 3, 4, 5] | |
| """ | |
| from sympy.combinatorics.perm_groups import PermutationGroup | |
| from sympy.combinatorics.tensor_can import gens_products, dummy_sgs | |
| from sympy.combinatorics.permutations import _af_rmul | |
| v1 = [] | |
| for i in range(len(v)): | |
| base_i, gens_i, n_i, sym_i = v[i] | |
| v1.append((base_i, gens_i, [[]]*n_i, sym_i)) | |
| size, sbase, sgens = gens_products(*v1) | |
| dgens = dummy_sgs(dummies, sym, size-2) | |
| if isinstance(sym, int): | |
| num_types = 1 | |
| dummies = [dummies] | |
| sym = [sym] | |
| else: | |
| num_types = len(sym) | |
| dgens = [] | |
| for i in range(num_types): | |
| dgens.extend(dummy_sgs(dummies[i], sym[i], size - 2)) | |
| S = PermutationGroup(sgens) | |
| D = PermutationGroup([Permutation(x) for x in dgens]) | |
| dlist = list(D.generate(af=True)) | |
| g = g.array_form | |
| st = set() | |
| for s in S.generate(af=True): | |
| h = _af_rmul(g, s) | |
| for d in dlist: | |
| q = tuple(_af_rmul(d, h)) | |
| st.add(q) | |
| a = list(st) | |
| a.sort() | |
| prev = (0,)*size | |
| for h in a: | |
| if h[:-2] == prev[:-2]: | |
| if h[-1] != prev[-1]: | |
| return 0 | |
| prev = h | |
| return list(a[0]) | |
| def graph_certificate(gr): | |
| """ | |
| Return a certificate for the graph | |
| Parameters | |
| ========== | |
| gr : adjacency list | |
| Explanation | |
| =========== | |
| The graph is assumed to be unoriented and without | |
| external lines. | |
| Associate to each vertex of the graph a symmetric tensor with | |
| number of indices equal to the degree of the vertex; indices | |
| are contracted when they correspond to the same line of the graph. | |
| The canonical form of the tensor gives a certificate for the graph. | |
| This is not an efficient algorithm to get the certificate of a graph. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.testutil import graph_certificate | |
| >>> gr1 = {0:[1, 2, 3, 5], 1:[0, 2, 4], 2:[0, 1, 3, 4], 3:[0, 2, 4], 4:[1, 2, 3, 5], 5:[0, 4]} | |
| >>> gr2 = {0:[1, 5], 1:[0, 2, 3, 4], 2:[1, 3, 5], 3:[1, 2, 4, 5], 4:[1, 3, 5], 5:[0, 2, 3, 4]} | |
| >>> c1 = graph_certificate(gr1) | |
| >>> c2 = graph_certificate(gr2) | |
| >>> c1 | |
| [0, 2, 4, 6, 1, 8, 10, 12, 3, 14, 16, 18, 5, 9, 15, 7, 11, 17, 13, 19, 20, 21] | |
| >>> c1 == c2 | |
| True | |
| """ | |
| from sympy.combinatorics.permutations import _af_invert | |
| from sympy.combinatorics.tensor_can import get_symmetric_group_sgs, canonicalize | |
| items = list(gr.items()) | |
| items.sort(key=lambda x: len(x[1]), reverse=True) | |
| pvert = [x[0] for x in items] | |
| pvert = _af_invert(pvert) | |
| # the indices of the tensor are twice the number of lines of the graph | |
| num_indices = 0 | |
| for v, neigh in items: | |
| num_indices += len(neigh) | |
| # associate to each vertex its indices; for each line | |
| # between two vertices assign the | |
| # even index to the vertex which comes first in items, | |
| # the odd index to the other vertex | |
| vertices = [[] for i in items] | |
| i = 0 | |
| for v, neigh in items: | |
| for v2 in neigh: | |
| if pvert[v] < pvert[v2]: | |
| vertices[pvert[v]].append(i) | |
| vertices[pvert[v2]].append(i+1) | |
| i += 2 | |
| g = [] | |
| for v in vertices: | |
| g.extend(v) | |
| assert len(g) == num_indices | |
| g += [num_indices, num_indices + 1] | |
| size = num_indices + 2 | |
| assert sorted(g) == list(range(size)) | |
| g = Permutation(g) | |
| vlen = [0]*(len(vertices[0])+1) | |
| for neigh in vertices: | |
| vlen[len(neigh)] += 1 | |
| v = [] | |
| for i in range(len(vlen)): | |
| n = vlen[i] | |
| if n: | |
| base, gens = get_symmetric_group_sgs(i) | |
| v.append((base, gens, n, 0)) | |
| v.reverse() | |
| dummies = list(range(num_indices)) | |
| can = canonicalize(g, dummies, 0, *v) | |
| return can | |