def test_minimal_block():
    D = DihedralGroup(6)
    block_system = D.minimal_block([0,3])
    for i in range(3):
        assert block_system[i] == block_system[i+3]
    S = SymmetricGroup(6)
    assert S.minimal_block([0, 1]) == [0, 0, 0, 0, 0, 0]

def test_is_alt_sym():
    G = DihedralGroup(10)
    assert G.is_alt_sym() is False
    S = SymmetricGroup(10)
    N_eps = 10
    _random_prec = {'N_eps': N_eps,
        0: Permutation([[2], [1, 4], [0, 6, 7, 8, 9, 3, 5]]),
        1: Permutation([[1, 8, 7, 6, 3, 5, 2, 9], [0, 4]]),
        2: Permutation([[5, 8], [4, 7], [0, 1, 2, 3, 6, 9]]),
        3: Permutation([[3], [0, 8, 2, 7, 4, 1, 6, 9, 5]]),
        4: Permutation([[8], [4, 7, 9], [3, 6], [0, 5, 1, 2]]),
        5: Permutation([[6], [0, 2, 4, 5, 1, 8, 3, 9, 7]]),
        6: Permutation([[6, 9, 8], [4, 5], [1, 3, 7], [0, 2]]),
        7: Permutation([[4], [0, 2, 9, 1, 3, 8, 6, 5, 7]]),
        8: Permutation([[1, 5, 6, 3], [0, 2, 7, 8, 4, 9]]),
        9: Permutation([[8], [6, 7], [2, 3, 4, 5], [0, 1, 9]])}
    assert S.is_alt_sym(_random_prec=_random_prec) is True
    A = AlternatingGroup(10)
    _random_prec = {'N_eps': N_eps,
        0: Permutation([[1, 6, 4, 2, 7, 8, 5, 9, 3], [0]]),
        1: Permutation([[1], [0, 5, 8, 4, 9, 2, 3, 6, 7]]),
        2: Permutation([[1, 9, 8, 3, 2, 5], [0, 6, 7, 4]]),
        3: Permutation([[6, 8, 9], [4, 5], [1, 3, 7, 2], [0]]),
        4: Permutation([[8], [5], [4], [2, 6, 9, 3], [1], [0, 7]]),
        5: Permutation([[3, 6], [0, 8, 1, 7, 5, 9, 4, 2]]),
        6: Permutation([[5], [2, 9], [1, 8, 3], [0, 4, 7, 6]]),
        7: Permutation([[1, 8, 4, 7, 2, 3], [0, 6, 9, 5]]),
        8: Permutation([[5, 8, 7], [3], [1, 4, 2, 6], [0, 9]]),
        9: Permutation([[4, 9, 6], [3, 8], [1, 2], [0, 5, 7]])}
    assert A.is_alt_sym(_random_prec=_random_prec) is False

def test_orbits():
    a = Permutation([2, 0, 1])
    b = Permutation([2, 1, 0])
    g = PermutationGroup([a, b])
    assert g.orbit(0) == {0, 1, 2}
    assert g.orbits() == [{0, 1, 2}]
    assert g.is_transitive() and g.is_transitive(strict=False)
    assert g.orbit_transversal(0) == \
        [Permutation(
            [0, 1, 2]), Permutation([2, 0, 1]), Permutation([1, 2, 0])]
    assert g.orbit_transversal(0, True) == \
        [(0, Permutation([0, 1, 2])), (2, Permutation([2, 0, 1])),
        (1, Permutation([1, 2, 0]))]

    G = DihedralGroup(6)
    transversal, slps = _orbit_transversal(G.degree, G.generators, 0, True, slp=True)
    for i, t in transversal:
        slp = slps[i]
        w = G.identity
        for s in slp:
            w = G.generators[s]*w
        assert w == t

    a = Permutation(list(range(1, 100)) + [0])
    G = PermutationGroup([a])
    assert [min(o) for o in G.orbits()] == [0]
    G = PermutationGroup(rubik_cube_generators())
    assert [min(o) for o in G.orbits()] == [0, 1]
    assert not G.is_transitive() and not G.is_transitive(strict=False)
    G = PermutationGroup([Permutation(0, 1, 3), Permutation(3)(0, 1)])
    assert not G.is_transitive() and G.is_transitive(strict=False)
    assert PermutationGroup(
        Permutation(3)).is_transitive(strict=False) is False

def test_center():
    # the center of the dihedral group D_n is of order 2 for even n
    for i in (4, 6, 10):
        D = DihedralGroup(i)
        assert (D.center()).order() == 2
    # the center of the dihedral group D_n is of order 1 for odd n>2
    for i in (3, 5, 7):
        D = DihedralGroup(i)
        assert (D.center()).order() == 1
    # the center of an abelian group is the group itself
    for i in (2, 3, 5):
        for j in (1, 5, 7):
            for k in (1, 1, 11):
                G = AbelianGroup(i, j, k)
                assert G.center().is_subgroup(G)
    # the center of a nonabelian simple group is trivial
    for i in(1, 5, 9):
        A = AlternatingGroup(i)
        assert (A.center()).order() == 1
    # brute-force verifications
    D = DihedralGroup(5)
    A = AlternatingGroup(3)
    C = CyclicGroup(4)
    G.is_subgroup(D*A*C)
    assert _verify_centralizer(G, G)

def test_schreier_vector():
    G = CyclicGroup(50)
    v = [0]*50
    v[23] = -1
    assert G.schreier_vector(23) == v
    H = DihedralGroup(8)
    assert H.schreier_vector(2) == [0, 1, -1, 0, 0, 1, 0, 0]
    L = SymmetricGroup(4)
    assert L.schreier_vector(1) == [1, -1, 0, 0]

def test_alt_or_sym():
    S = SymmetricGroup(10)
    A = AlternatingGroup(10)
    D = DihedralGroup(10)
    sym = S.alt_or_sym()
    alt = A.alt_or_sym()
    dih = D.alt_or_sym()
    assert sym == 'S' or sym == False
    assert alt == 'A' or alt == False
    assert dih == False

def test_random_pr():
    D = DihedralGroup(6)
    r = 11
    n = 3
    _random_prec_n = {}
    _random_prec_n[0] = {'s': 7, 't': 3, 'x': 2, 'e': -1}
    _random_prec_n[1] = {'s': 5, 't': 5, 'x': 1, 'e': -1}
    _random_prec_n[2] = {'s': 3, 't': 4, 'x': 2, 'e': 1}
    D._random_pr_init(r, n, _random_prec_n=_random_prec_n)
    assert D._random_gens[11] == [0, 1, 2, 3, 4, 5]
    _random_prec = {'s': 2, 't': 9, 'x': 1, 'e': -1}
    assert D.random_pr(_random_prec=_random_prec) == \
        Permutation([0, 5, 4, 3, 2, 1])

def test_remove_gens():
    S = SymmetricGroup(10)
    base, strong_gens = S.schreier_sims_incremental()
    new_gens = _remove_gens(base, strong_gens)
    assert _verify_bsgs(S, base, new_gens) is True
    A = AlternatingGroup(7)
    base, strong_gens = A.schreier_sims_incremental()
    new_gens = _remove_gens(base, strong_gens)
    assert _verify_bsgs(A, base, new_gens) is True
    D = DihedralGroup(2)
    base, strong_gens = D.schreier_sims_incremental()
    new_gens = _remove_gens(base, strong_gens)
    assert _verify_bsgs(D, base, new_gens) is True

def test_minimal_block():
    D = DihedralGroup(6)
    block_system = D.minimal_block([0, 3])
    for i in range(3):
        assert block_system[i] == block_system[i + 3]
    S = SymmetricGroup(6)
    assert S.minimal_block([0, 1]) == [0, 0, 0, 0, 0, 0]

    assert Tetra.pgroup.minimal_block([0, 1]) == [0, 0, 0, 0]

    P1 = PermutationGroup(Permutation(1, 5)(2, 4), Permutation(0, 1, 2, 3, 4, 5))
    P2 = PermutationGroup(Permutation(0, 1, 2, 3, 4, 5), Permutation(1, 5)(2, 4))
    assert P1.minimal_block([0, 2]) == [0, 3, 0, 3, 0, 3]
    assert P2.minimal_block([0, 2]) == [0, 3, 0, 3, 0, 3]

def test_schreier_sims_random():
    S = SymmetricGroup(3)
    base = [0, 1]
    strong_gens = [Permutation([1, 2, 0]), Permutation([1, 0, 2]),\
                  Permutation([0, 2, 1])]
    assert S.schreier_sims_random(base, strong_gens, 5) == (base, strong_gens)
    D = DihedralGroup(3)
    _random_prec = {'g': [Permutation([2, 0, 1]), Permutation([1, 2, 0]),\
                         Permutation([1, 0, 2])]}
    base = [0, 1]
    strong_gens = [Permutation([1, 2, 0]), Permutation([2, 1, 0]),\
                  Permutation([0, 2, 1])]
    assert D.schreier_sims_random([], D.generators, 2,\
           _random_prec=_random_prec) == (base, strong_gens)

def test_strip():
    D = DihedralGroup(5)
    D.schreier_sims()
    member = Permutation([4, 0, 1, 2, 3])
    not_member1 = Permutation([0, 1, 4, 3, 2])
    not_member2 = Permutation([3, 1, 4, 2, 0])
    identity = Permutation([0, 1, 2, 3, 4])
    res1 = _strip(member, D.base, D.basic_orbits, D.basic_transversals)
    res2 = _strip(not_member1, D.base, D.basic_orbits, D.basic_transversals)
    res3 = _strip(not_member2, D.base, D.basic_orbits, D.basic_transversals)
    assert res1[0] == identity
    assert res1[1] == len(D.base) + 1
    assert res2[0] == not_member1
    assert res2[1] == len(D.base) + 1
    assert res3[0] != identity
    assert res3[1] == 2

def test_centralizer():
    # the centralizer of the trivial group is the entire group
    S = SymmetricGroup(2)
    assert S.centralizer(Permutation(list(range(2)))).is_subgroup(S)
    A = AlternatingGroup(5)
    assert A.centralizer(Permutation(list(range(5)))).is_subgroup(A)
    # a centralizer in the trivial group is the trivial group itself
    triv = PermutationGroup([Permutation([0, 1, 2, 3])])
    D = DihedralGroup(4)
    assert triv.centralizer(D).is_subgroup(triv)
    # brute-force verifications for centralizers of groups
    for i in (4, 5, 6):
        S = SymmetricGroup(i)
        A = AlternatingGroup(i)
        C = CyclicGroup(i)
        D = DihedralGroup(i)
        for gp in (S, A, C, D):
            for gp2 in (S, A, C, D):
                if not gp2.is_subgroup(gp):
                    assert _verify_centralizer(gp, gp2)
    # verify the centralizer for all elements of several groups
    S = SymmetricGroup(5)
    elements = list(S.generate_dimino())
    for element in elements:
        assert _verify_centralizer(S, element)
    A = AlternatingGroup(5)
    elements = list(A.generate_dimino())
    for element in elements:
        assert _verify_centralizer(A, element)
    D = DihedralGroup(7)
    elements = list(D.generate_dimino())
    for element in elements:
        assert _verify_centralizer(D, element)
    # verify centralizers of small groups within small groups
    small = []
    for i in (1, 2, 3):
        small.append(SymmetricGroup(i))
        small.append(AlternatingGroup(i))
        small.append(DihedralGroup(i))
        small.append(CyclicGroup(i))
    for gp in small:
        for gp2 in small:
            if gp.degree == gp2.degree:
                assert _verify_centralizer(gp, gp2)

def test_DihedralGroup():
    G = DihedralGroup(6)
    elements = list(G.generate())
    assert len(elements) == 12
    assert G.is_transitive() is True
    assert G.is_abelian is False
    H = DihedralGroup(1)
    assert H.order() == 2
    L = DihedralGroup(2)
    assert L.order() == 4
    assert L.is_abelian is True

def test_schreier_sims_incremental():
    identity = Permutation([0, 1, 2, 3, 4])
    TrivialGroup = PermutationGroup([identity])
    base, strong_gens = TrivialGroup.schreier_sims_incremental(base=[0, 1, 2])
    assert _verify_bsgs(TrivialGroup, base, strong_gens) is True
    S = SymmetricGroup(5)
    base, strong_gens = S.schreier_sims_incremental(base=[0, 1, 2])
    assert _verify_bsgs(S, base, strong_gens) is True
    D = DihedralGroup(2)
    base, strong_gens = D.schreier_sims_incremental(base=[1])
    assert _verify_bsgs(D, base, strong_gens) is True
    A = AlternatingGroup(7)
    gens = A.generators[:]
    gen0 = gens[0]
    gen1 = gens[1]
    gen1 = rmul(gen1, ~gen0)
    gen0 = rmul(gen0, gen1)
    gen1 = rmul(gen0, gen1)
    base, strong_gens = A.schreier_sims_incremental(base=[0, 1], gens=gens)
    assert _verify_bsgs(A, base, strong_gens) is True
    C = CyclicGroup(11)
    gen = C.generators[0]
    base, strong_gens = C.schreier_sims_incremental(gens=[gen**3])
    assert _verify_bsgs(C, base, strong_gens) is True

def test_orbit_rep():
    G = DihedralGroup(6)
    assert G.orbit_rep(1, 3) in [Permutation([2, 3, 4, 5, 0, 1]),
    Permutation([4, 3, 2, 1, 0, 5])]
    H = CyclicGroup(4)*G
    assert H.orbit_rep(1, 5) is False