def descendant_subgroups(S, C, R1_c_list, x, R2, N, Y):
    A_dict = C.A_dict
    A_dict_inv = C.A_dict_inv
    if C.is_complete():
        # if C is complete then it only needs to test
        # whether the relators in R2 are satisfied
        for w, alpha in product(R2, C.omega):
            if not C.scan_check(alpha, w):
                return
        # relators in R2 are satisfied, append the table to list
        S.append(C)
    else:
        # find the first undefined entry in Coset Table
        for alpha, x in product(range(len(C.table)), C.A):
            if C.table[alpha][A_dict[x]] is None:
                # this is "x" in pseudo-code (using "y" makes it clear)
                undefined_coset, undefined_gen = alpha, x
                break
        # for filling up the undefine entry we try all possible values
        # of β ∈ Ω or β = n where β^(undefined_gen^-1) is undefined
        reach = C.omega + [C.n]
        for beta in reach:
            if beta < N:
                if beta == C.n or C.table[beta][A_dict_inv[undefined_gen]] is None:
                    try_descendant(S, C, R1_c_list, R2, N, undefined_coset, \
                            undefined_gen, beta, Y)

def test_function_subs():
    f = Function("f")
    S = Sum(x*f(y),(x,0,oo),(y,0,oo))
    assert S.subs(f(y),y) == Sum(x*y,(x,0,oo),(y,0,oo))
    assert S.subs(f(x),x) == S
    raises(ValueError, lambda: S.subs(f(y),x+y) )
    S = Sum(x*log(y),(x,0,oo),(y,0,oo))
    assert S.subs(log(y),y) == S
    S = Sum(x*f(y),(x,0,oo),(y,0,oo))
    assert S.subs(f(y),y) == Sum(x*y,(x,0,oo),(y,0,oo))

def test_exceptions():
    S = Sum(x, (x, a, b))
    raises(ValueError, lambda: S.change_index(x, x**2, y))
    S = Sum(x, (x, a, b), (x, 1, 4))
    raises(ValueError, lambda: S.index(x))
    S = Sum(x, (x, a, b), (y, 1, 4))
    raises(ValueError, lambda: S.reorder([x]))
    S = Sum(x, (x, y, b), (y, 1, 4))
    raises(ReorderError, lambda: S.reorder_limit(0, 1))
    S = Sum(x*y, (x, a, b), (y, 1, 4))
    raises(NotImplementedError, lambda: S.is_convergent())

def test_permutation_methods():
    from sympy.combinatorics.fp_groups import FpSubgroup
    F, x, y = free_group("x, y")
    # DihedralGroup(8)
    G = FpGroup(F, [x**2, y**8, x*y*x**-1*y])
    T = G._to_perm_group()[1]
    assert T.is_isomorphism()
    assert G.center() == [y**4]

    # DiheadralGroup(4)
    G = FpGroup(F, [x**2, y**4, x*y*x**-1*y])
    S = FpSubgroup(G, G.normal_closure([x]))
    assert x in S
    assert y**-1*x*y in S

    # Z_5xZ_4
    G = FpGroup(F, [x*y*x**-1*y**-1, y**5, x**4])
    assert G.is_abelian
    assert G.is_solvable

    # AlternatingGroup(5)
    G = FpGroup(F, [x**3, y**2, (x*y)**5])
    assert not G.is_solvable

    # AlternatingGroup(4)
    G = FpGroup(F, [x**3, y**2, (x*y)**3])
    assert len(G.derived_series()) == 3
    S = FpSubgroup(G, G.derived_subgroup())
    assert S.order() == 4

def test_Sum_doit():
    assert Sum(n * Integral(a ** 2), (n, 0, 2)).doit() == a ** 3
    assert Sum(n * Integral(a ** 2), (n, 0, 2)).doit(deep=False) == 3 * Integral(a ** 2)
    assert summation(n * Integral(a ** 2), (n, 0, 2)) == 3 * Integral(a ** 2)

    # test nested sum evaluation
    S = Sum(Sum(Sum(2, (z, 1, n + 1)), (y, x + 1, n)), (x, 1, n))
    assert 0 == (S.doit() - n * (n + 1) * (n - 1)).factor()

    def test_PQ_f7(self):
        S = QQ['t']
        t = S.gen()
        r0,r1,r2 = (t**3 - t**2 + 1).roots(QQbar, multiplicities=False)

        series = self.get_PQ(self.f7)
        x,y = self.f7.parent().gens()
        x = QQbar['x,y'](x)
        y = QQbar['x,y'](y)
        self.assertItemsEqual(
            series,
            [(x, y + r0),
             (x, y + r1),
             (x, y + r2)])

    def update(f, sugar, P):
        """Add f with sugar ``sugar`` to S, update P."""
        if not f:
            return P
        k = len(S)
        S.append(f)
        Sugars.append(sugar)

        LMf = sdm_LM(f)

        def removethis(pair):
            i, j, s, t = pair
            if LMf[0] != t[0]:
                return False
            tik = sdm_monomial_lcm(LMf, sdm_LM(S[i]))
            tjk = sdm_monomial_lcm(LMf, sdm_LM(S[j]))
            return tik != t and tjk != t and sdm_monomial_divides(tik, t) and \
                sdm_monomial_divides(tjk, t)
        # apply the chain criterion
        P = [p for p in P if not removethis(p)]

        # new-pair set
        N = [(i, k, Ssugar(i, k), sdm_monomial_lcm(LMf, sdm_LM(S[i])))
             for i in range(k) if LMf[0] == sdm_LM(S[i])[0]]
        # TODO apply the product criterion?
        N.sort(key=ourkey)
        remove = set()
        for i, p in enumerate(N):
            for j in range(i + 1, len(N)):
                if sdm_monomial_divides(p[3], N[j][3]):
                    remove.add(j)

        # TODO mergesort?
        P.extend(reversed([p for i, p in enumerate(N) if not i in remove]))
        P.sort(key=ourkey, reverse=True)
        # NOTE reverse-sort, because we want to pop from the end
        return P

    def test_PQ_f27(self):
        S = QQ['t']
        t = S.gen()
        sqrt2 = (t**2 - 2).roots(QQbar, multiplicities=False)[0]

        series = self.get_PQ(self.f27)
        x,y = self.f27.parent().gens()
        x = QQbar['x,y'](x)
        y = QQbar['x,y'](y)
        self.assertItemsEqual(
            series,
            [(x, x*(y + sqrt2)),
             (x, x*(y - sqrt2)),
             (x**2/2, x**3*(y + 1)/2),
             (x**3/2, x*(y + 1))])

def test_sparse_matrix():
    def sparse_eye(n):
        return SparseMatrix.eye(n)

    def sparse_zeros(n):
        return SparseMatrix.zeros(n)

    # creation args
    raises(TypeError, lambda: SparseMatrix(1, 2))

    a = SparseMatrix((
        (1, 0),
        (0, 1)
    ))
    assert SparseMatrix(a) == a

    from sympy.matrices import MutableSparseMatrix, MutableDenseMatrix
    a = MutableSparseMatrix([])
    b = MutableDenseMatrix([1, 2])
    assert a.row_join(b) == b
    assert a.col_join(b) == b
    assert type(a.row_join(b)) == type(a)
    assert type(a.col_join(b)) == type(a)

    # make sure 0 x n matrices get stacked correctly
    sparse_matrices = [SparseMatrix.zeros(0, n) for n in range(4)]
    assert SparseMatrix.hstack(*sparse_matrices) == Matrix(0, 6, [])
    sparse_matrices = [SparseMatrix.zeros(n, 0) for n in range(4)]
    assert SparseMatrix.vstack(*sparse_matrices) == Matrix(6, 0, [])

    # test element assignment
    a = SparseMatrix((
        (1, 0),
        (0, 1)
    ))

    a[3] = 4
    assert a[1, 1] == 4
    a[3] = 1

    a[0, 0] = 2
    assert a == SparseMatrix((
        (2, 0),
        (0, 1)
    ))
    a[1, 0] = 5
    assert a == SparseMatrix((
        (2, 0),
        (5, 1)
    ))
    a[1, 1] = 0
    assert a == SparseMatrix((
        (2, 0),
        (5, 0)
    ))
    assert a._smat == {(0, 0): 2, (1, 0): 5}

    # test_multiplication
    a = SparseMatrix((
        (1, 2),
        (3, 1),
        (0, 6),
    ))

    b = SparseMatrix((
        (1, 2),
        (3, 0),
    ))

    c = a*b
    assert c[0, 0] == 7
    assert c[0, 1] == 2
    assert c[1, 0] == 6
    assert c[1, 1] == 6
    assert c[2, 0] == 18
    assert c[2, 1] == 0

    try:
        eval('c = a @ b')
    except SyntaxError:
        pass
    else:
        assert c[0, 0] == 7
        assert c[0, 1] == 2
        assert c[1, 0] == 6
        assert c[1, 1] == 6
        assert c[2, 0] == 18
        assert c[2, 1] == 0

    x = Symbol("x")

    c = b * Symbol("x")
    assert isinstance(c, SparseMatrix)
    assert c[0, 0] == x
    assert c[0, 1] == 2*x
    assert c[1, 0] == 3*x
    assert c[1, 1] == 0

    c = 5 * b
    assert isinstance(c, SparseMatrix)
#.........这里部分代码省略.........

 def _test_subgroup(K, T, S):
     _gens = T(K.generators)
     assert all(elem in S for elem in _gens)
     assert T.is_injective()
     assert T.image().order() == S.order()

def sdm_groebner(G, NF, O, K, extended=False):
    """
    Compute a minimal standard basis of ``G`` with respect to order ``O``.

    The algorithm uses a normal form ``NF``, for example ``sdm_nf_mora``.
    The ground field is assumed to be ``K``, and monomials ordered according
    to ``O``.

    Let `N` denote the submodule generated by elements of `G`. A standard
    basis for `N` is a subset `S` of `N`, such that `in(S) = in(N)`, where for
    any subset `X` of `F`, `in(X)` denotes the submodule generated by the
    initial forms of elements of `X`. [SCA, defn 2.3.2]

    A standard basis is called minimal if no subset of it is a standard basis.

    One may show that standard bases are always generating sets.

    Minimal standard bases are not unique. This algorithm computes a
    deterministic result, depending on the particular order of `G`.

    If ``extended=True``, also compute the transition matrix from the initial
    generators to the groebner basis. That is, return a list of coefficient
    vectors, expressing the elements of the groebner basis in terms of the
    elements of ``G``.

    This functions implements the "sugar" strategy, see

    Giovini et al: "One sugar cube, please" OR Selection strategies in
    Buchberger algorithm.
    """

    # The critical pair set.
    # A critical pair is stored as (i, j, s, t) where (i, j) defines the pair
    # (by indexing S), s is the sugar of the pair, and t is the lcm of their
    # leading monomials.
    P = []

    # The eventual standard basis.
    S = []
    Sugars = []

    def Ssugar(i, j):
        """Compute the sugar of the S-poly corresponding to (i, j)."""
        LMi = sdm_LM(S[i])
        LMj = sdm_LM(S[j])
        return max(Sugars[i] - sdm_monomial_deg(LMi),
                   Sugars[j] - sdm_monomial_deg(LMj)) \
            + sdm_monomial_deg(sdm_monomial_lcm(LMi, LMj))

    ourkey = lambda p: (p[2], O(p[3]), p[1])

    def update(f, sugar, P):
        """Add f with sugar ``sugar`` to S, update P."""
        if not f:
            return P
        k = len(S)
        S.append(f)
        Sugars.append(sugar)

        LMf = sdm_LM(f)

        def removethis(pair):
            i, j, s, t = pair
            if LMf[0] != t[0]:
                return False
            tik = sdm_monomial_lcm(LMf, sdm_LM(S[i]))
            tjk = sdm_monomial_lcm(LMf, sdm_LM(S[j]))
            return tik != t and tjk != t and sdm_monomial_divides(tik, t) and \
                sdm_monomial_divides(tjk, t)
        # apply the chain criterion
        P = [p for p in P if not removethis(p)]

        # new-pair set
        N = [(i, k, Ssugar(i, k), sdm_monomial_lcm(LMf, sdm_LM(S[i])))
             for i in range(k) if LMf[0] == sdm_LM(S[i])[0]]
        # TODO apply the product criterion?
        N.sort(key=ourkey)
        remove = set()
        for i, p in enumerate(N):
            for j in range(i + 1, len(N)):
                if sdm_monomial_divides(p[3], N[j][3]):
                    remove.add(j)

        # TODO mergesort?
        P.extend(reversed([p for i, p in enumerate(N) if not i in remove]))
        P.sort(key=ourkey, reverse=True)
        # NOTE reverse-sort, because we want to pop from the end
        return P

    # Figure out the number of generators in the ground ring.
    try:
        # NOTE: we look for the first non-zero vector, take its first monomial
        #       the number of generators in the ring is one less than the length
        #       (since the zeroth entry is for the module generators)
        numgens = len(next(x[0] for x in G if x)[0]) - 1
    except StopIteration:
        # No non-zero elements in G ...
        if extended:
            return [], []
        return []
#.........这里部分代码省略.........

def sdm_groebner(G, NF, O, K):
    """
    Compute a minimal standard basis of ``G`` with respect to order ``O``.

    The algorithm uses a normal form ``NF``, for example ``sdm_nf_mora``.
    The ground field is assumed to be ``K``, and monomials ordered according
    to ``O``.

    Let `N` denote the submodule generated by elements of `G`. A standard
    basis for `N` is a subset `S` of `N`, such that `in(S) = in(N)`, where for
    any subset `X` of `F`, `in(X)` denotes the submodule generated by the
    initial forms of elements of `X`. [SCA, defn 2.3.2]

    A standard basis is called minimal if no subset of it is a standard basis.

    One may show that standard bases are always generating sets.

    Minimal standard bases are not unique. This algorithm computes a
    deterministic result, depending on the particular order of `G`.

    See [SCA, algorithm 2.3.8, and remark 1.6.3].
    """
    # First compute a standard basis
    S = [f for f in G if f]
    P = list(combinations(S, 2))

    def prune(P, S, h):
        """
        Prune the pair-set by applying the chain criterion
        [SCA, remark 2.5.11].
        """
        remove = set()
        retain = set()
        for (a, b, c) in permutations(S, 3):
            A = sdm_LM(a)
            B = sdm_LM(b)
            C = sdm_LM(c)
            if len(set([A[0], B[0], C[0]])) != 1 or not h in [a, b, c] or \
               any(tuple(x) in retain for x in [a, b, c]):
                continue
            if monomial_divides(B[1:], monomial_lcm(A[1:], C[1:])):
                remove.add((tuple(a), tuple(c)))
                retain.update([tuple(b), tuple(c), tuple(a)])
        return [(f, g) for (f, g) in P if (h not in [f, g]) or \
                    ((tuple(f), tuple(g)) not in remove and \
                     (tuple(g), tuple(f)) not in remove)]

    while P:
        # TODO better data structures!!!
        #print len(P), len(S)
        # Use the "normal selection strategy"
        lcms = [(i, sdm_LM(f)[:1] + monomial_lcm(sdm_LM(f)[1:], sdm_LM(g)[1:])) for \
                i, (f, g) in enumerate(P)]
        i = min(lcms, key=lambda x: O(x[1]))[0]
        f, g = P.pop(i)
        h = NF(sdm_spoly(f, g, O, K), S, O, K)
        if h:
            S.append(h)
            P.extend((h, f) for f in S if sdm_LM(h)[0] == sdm_LM(f)[0])
            P = prune(P, S, h)

    # Now interreduce it. (TODO again, better data structures)
    S = set(tuple(f) for f in S)
    for a, b in permutations(S, 2):
        A = sdm_LM(list(a))
        B = sdm_LM(list(b))
        if sdm_monomial_divides(A, B) and b in S and a in S:
            S.remove(b)

    return sorted((list(f) for f in S), key=lambda f: O(sdm_LM(f)),
                  reverse=True)

from sage.all import SR
from sage.calculus.functional import taylor
from sage.calculus.var import var
from sage.rings.arith import xgcd
from sage.rings.laurent_series_ring import LaurentSeriesRing
from sage.rings.rational_field import QQ
from sage.rings.qqbar import QQbar
from sage.rings.infinity import infinity
from sympy import Poly, Point, Segment, Polygon, RootOf, sqrt, S

# every example will be over QQ[x,y]. consider putting in setup?
R = QQ['x,y']
S = QQ['t']
x,y = R.gens()
t = S.gens()

class TestNewtonPolygon(unittest.TestCase):

    def test_segment(self):
        H = y + x
        self.assertEqual(newton_polygon(H),
                         [[(0,1),(1,0)]])

        H = y**2 + x**2
        self.assertEqual(newton_polygon(H),
                         [[(0,2),(2,0)]])

    def test_general_segment(self):
        H = y**2 + x**4
        self.assertEqual(newton_polygon(H),