|
|
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) |
|
|
|
|
|
|
|
|
num_indices = 0 |
|
|
for v, neigh in items: |
|
|
num_indices += len(neigh) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |
|
|
|
