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.

    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.

    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.

    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():
        for gen in subgr_gens:
            conjugates.add(gen ^ el)
    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

    g  permutation representing the tensor
    dummies  list of dummy indices
    msym symmetry of the metric

    v is 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 ot tensors of type `i`

    sym_i symmetry under exchange of two component tensors of type `i`
          None  no symmetry
          0     commuting
          1     anticommuting

    Return 0 if the tensor is zero, else return 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, PermutationGroup
    >>> 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 Permutation, _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

    gr adjacency list

    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

[((104, 24, 104, 60), 'sympy.combinatorics.util._distribute_gens_by_base', '_distribute_gens_by_base', ({(104, 49, 104, 53): 'base', (104, 55, 104, 59): 'gens'}, {}), '(base, gens)', False, 'from sympy.combinatorics.util import _distribute_gens_by_base\n'), ((231, 25, 231, 43), 'sympy.combinatorics.tensor_can.gens_products', 'gens_products', ({(231, 39, 231, 42): '*v1'}, {}), '(*v1)', False, 'from sympy.combinatorics.tensor_can import gens_products, dummy_sgs\n'), ((232, 12, 232, 43), 'sympy.combinatorics.tensor_can.dummy_sgs', 'dummy_sgs', ({(232, 22, 232, 29): 'dummies', (232, 31, 232, 34): 'sym', (232, 36, 232, 42): 'size - 2'}, {}), '(dummies, sym, size - 2)', False, 'from sympy.combinatorics.tensor_can import gens_products, dummy_sgs\n'), ((242, 8, 242, 31), 'sympy.combinatorics.perm_groups.PermutationGroup', 'PermutationGroup', ({(242, 25, 242, 30): 'sgens'}, {}), '(sgens)', False, 'from sympy.combinatorics.perm_groups import PermutationGroup\n'), ((297, 12, 297, 29), 'sympy.combinatorics.permutations._af_invert', '_af_invert', ({(297, 23, 297, 28): 'pvert'}, {}), '(pvert)', False, 'from sympy.combinatorics.permutations import _af_invert\n'), ((322, 8, 322, 22), 'sympy.combinatorics.permutations.Permutation', 'Permutation', ({(322, 20, 322, 21): 'g'}, {}), '(g)', False, 'from sympy.combinatorics.permutations import Permutation, _af_rmul\n'), ((334, 10, 334, 41), 'sympy.combinatorics.tensor_can.canonicalize', 'canonicalize', ({(334, 23, 334, 24): 'g', (334, 26, 334, 33): 'dummies', (334, 35, 334, 36): '0', (334, 38, 334, 40): '*v'}, {}), '(g, dummies, 0, *v)', False, 'from sympy.combinatorics.tensor_can import get_symmetric_group_sgs, canonicalize\n'), ((107, 20, 107, 58), 'sympy.combinatorics.perm_groups.PermutationGroup', 'PermutationGroup', ({(107, 37, 107, 57): 'strong_gens_distr[i]'}, {}), '(strong_gens_distr[i])', False, 'from sympy.combinatorics.perm_groups import PermutationGroup\n'), ((248, 12, 248, 26), 'sympy.combinatorics.permutations._af_rmul', '_af_rmul', ({(248, 21, 248, 22): 'g', (248, 24, 248, 25): 's'}, {}), '(g, s)', False, 'from sympy.combinatorics.permutations import Permutation, _af_rmul\n'), ((241, 21, 241, 60), 'sympy.combinatorics.tensor_can.dummy_sgs', 'dummy_sgs', ({(241, 31, 241, 41): 'dummies[i]', (241, 43, 241, 49): 'sym[i]', (241, 51, 241, 59): '(size - 2)'}, {}), '(dummies[i], sym[i], size - 2)', False, 'from sympy.combinatorics.tensor_can import gens_products, dummy_sgs\n'), ((243, 26, 243, 40), 'sympy.combinatorics.permutations.Permutation', 'Permutation', ({(243, 38, 243, 39): 'x'}, {}), '(x)', False, 'from sympy.combinatorics.permutations import Permutation, _af_rmul\n'), ((330, 25, 330, 51), 'sympy.combinatorics.tensor_can.get_symmetric_group_sgs', 'get_symmetric_group_sgs', ({(330, 49, 330, 50): 'i'}, {}), '(i)', False, 'from sympy.combinatorics.tensor_can import get_symmetric_group_sgs, canonicalize\n'), ((73, 45, 73, 68), 'sympy.combinatorics.perm_groups.PermutationGroup', 'PermutationGroup', ({(73, 62, 73, 67): 'other'}, {}), '(other)', False, 'from sympy.combinatorics.perm_groups import PermutationGroup\n'), ((250, 22, 250, 36), 'sympy.combinatorics.permutations._af_rmul', '_af_rmul', ({(250, 31, 250, 32): 'd', (250, 34, 250, 35): 'h'}, {}), '(d, h)', False, 'from sympy.combinatorics.permutations import Permutation, _af_rmul\n'), ((61, 43, 61, 68), 'sympy.combinatorics.permutations._af_commutes_with', '_af_commutes_with', ({(61, 61, 61, 62): 'x', (61, 64, 61, 67): 'gen'}, {}), '(x, gen)', False, 'from sympy.combinatorics.permutations import _af_commutes_with\n'), ((75, 45, 75, 70), 'sympy.combinatorics.perm_groups.PermutationGroup', 'PermutationGroup', ({(75, 62, 75, 69): '[other]'}, {}), '([other])', False, 'from sympy.combinatorics.perm_groups import PermutationGroup\n'), ((66, 44, 66, 72), 'sympy.combinatorics.permutations.Permutation._af_new', 'Permutation._af_new', ({(66, 64, 66, 71): 'element'}, {}), '(element)', False, 'from sympy.combinatorics.permutations import Permutation, _af_rmul\n')]