# This file contains a general purpose function to compute the orbit
# of an element under the action of a group.

# More precisely, it takes the following two inputs:

# begin = A set of elements

# homs = A dictionary of operators indexed by some keys (keys are irrelevant).

# and outputs a set of all x of the form x = f(y) where y is in begin
# and f is a composition of elements in homs.  In a typical
# application, begin will be a singleton set, in which case the answer
# is the orbit of its element under the semi-group generated by homs.

# Assumptions and caveats.

# We assume that the elements of begin are elements of some ring.  In
# particular, we assume that there is a way to "expand" them.
# Furthermore, we assume that after expanding, they are faithfully
# hashable.  We work with a "set" of these elements and assume that
# the set operations work as advertised.

def computeOrbit(begin, homs):
    # We call elements of begin "equations".
    equations = begin.copy()    
    # "Symmetrizing" eq means computing h(eq) for all h in homs.
    toSymmetrize = begin.copy()
    # toSymmetrize keeps a set of equations that are yet to be
    # symmetrized.  In the beginning, it is just a copy of the set of
    # equations.
    
    # symmetrized keeps a set of the equations that have been symmetrized
    symmetrized = set([])

    while len(toSymmetrize) > 0:
        # Pick the first equation to be symmetrized
        eq = toSymmetrize.pop()
        
        # Add to equations the previously unseen equations obtained by
        # applying the homomorphisms to eq.  Also add to toSymmetrize
        # these equations.
        for h in homs.values():
        #   print "here1"
            newEq = expand(h(eq))
        #   print "here2"
            if newEq not in equations:
                equations.add(newEq)
        #   print "here3"
            if newEq != eq and newEq not in toSymmetrize and newEq not in symmetrized:
                toSymmetrize.add(newEq)
        #   print "here4"
        # Now eq has been symmetrized. Add eq to the set of
        # symmetrized equations
        symmetrized.add(eq)
                    
        print "Found: " + str(len(equations))
        print "To symmetrize: " + str(len(toSymmetrize))
        print "Symmetrized: " + str(len(symmetrized))
        print " "

    return equations