## NOTE: This will not run without the permpy library installed. See http://permpy.com.

from permpy import *
import itertools
import sympy
import math

donesofar = 0

# Check if two functions are equal by subtracting, simplifying, and comparing to 0
def check_form(thing_to_check, form):
	return sympy.simplify(thing_to_check - form) == 0

# The aim of this function is to build all maximal classes whose SI sequence starts
# 1, 1, 2, 3, 4, 4, and then identify which of them ever have an entry greater than 4
# in their SI sequence. The result is that only two do, Sub(U) and its symmetry under
# inverse.

# For a non-verbose output that only prints the classes that are found to have a 5,
# run the command 
#       check_class(Av([]))
# To run in verbose mode where all maximal classes are displayed along with their
# generating functions, run the command
#       check_class(Av([]), verbose=True)
def check_class(C, start_seq=[0,1,1,2,3,4,4], verbose=False):
	global donesofar
	
	# We first calculate the SI sequence of the class
	si_spec = [len([P for P in C[i] if not P.sum_decomposable()]) for i in range(len(C))]
	if verbose:
		print '\nExamining the class Av(',C.basis,').\n\tThe SI sequence is: ',si_spec[1:]

	# If the SI sequence starts correctly, then we try to find the generating function
	# with the insertion encoding and compare it to known forms (i.e., the sequence
	# 1, 1, 2, 3, 4^*). If it doesn't match one of these, we print it out to be checked
	# by hand.
	if si_spec[:len(start_seq)] == start_seq:
		donesofar += 1
		
		if verbose:
			print '\tThe SI sequence starts',start_seq[1:],' so we attempt to enumerate.'
		I = InsertionScheme(C.basis)
		f = I.gf()
		g = 1-1/f
		g_copy = sympy.simplify(g)
		h = g.series(n=12)
		x = sympy.Symbol('x')

		i = 0
		while True:
			if h.coeff(x,i) < 4 and i < 8:
				g -= h.coeff(x,i)*x**i
				i += 1
			else:
				break
		
		g = sympy.simplify(g)

		if verbose:
			print '\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~'
			print '\t Completed Class #: ',donesofar
			print '\t\tEnumerated Successfully'
			print '\n\t\tGF: ',g_copy
			print '\n\t\tInitial terms: ',h
			if sympy.denom(g) == 1 or check_form(g, 4*x**5/(1-x)) or check_form(g, x**5*(x**2 - 4)/(x - 1)):
				print '\n\t\tForm recognized, no 5s present.'
			else:
				print '\n\t\tForm not recognized, should be checked by hand for 5s.'
				print '\t\t\t',g
			print '\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~'
		else:
			if not (sympy.denom(g) == 1 or check_form(g, 4*x**5/(1-x)) or check_form(g, x**5*(x**2 - 4)/(x - 1))):
				print '\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~'
				print '\t Class to be checked by hand.'
				print '\t\tAv(',C.basis,')'
				print '\t\tEnumerated Successfully'
				print '\n\t\tGF: ',g_copy
				print '\n\t\tInitial terms: ',h
				print '\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~'
	# If the SI sequence does not yet match the specified starting sequence, we find the first place where it
	# disagrees and add all combinations of as many permutations of that length to the basis to make it agree.
	else:
		for (pos, val) in enumerate(start_seq):
			if pos == len(C) - 1:
				print '\tneed to go longer!'
			if si_spec[pos] > val:
				diff = si_spec[pos] - val
				
				new_class_basis_additions = list(itertools.combinations([P for P in C[pos] if not P.sum_decomposable()], diff))
				if verbose:
					print '\tWe need to add',diff,'SI permutations of length',pos,'to the basis.'
				new_classes = []
				for B in new_class_basis_additions:
					new_classes.append(Av(C.basis+list(B), 10))

				for D in new_classes:
					check_class(D, start_seq, verbose)
				return