IntegerPartitionPatterns.py

import itertools 
import copy
import time,sys
import multiprocessing as mp


# code for Rook-equivalence

def GetHiddenRows(mu):
	h = len(mu)
	H = []

	for i in range(0,h):
		if mu[h-i-1] > len(H):
			H.append(h-1-i)
	return H

def GetMultiSetHiddenL(mu):
	M = []
	R = GetHiddenRows(mu)
	for r in R:
		M.append(r+mu[r])
	return sorted(M)
		
def GetRookClasses(n):
	D={}
	for mu in Partitions(n):
		k = str(GetMultiSetHiddenL(mu))
		if D.has_key(k):
			D[k].append(mu)
		else:
			D[k] = [mu]
	return D		


# code for Wilf-equivalence
def NumberPartsOfSize(mu,k):
	return len([p for p in list(mu) if p==k])

def PartitionsInRectangleFixedTop(top,h):
	P = []
	if top ==0:
		return [Partition([])]

	for weight in range(top,top*h+1):
		for mu in Partitions(weight, max_length = h):
			if  mu[0] == top:
				P.append(mu)

	return P			
	
def PartitionAvoids(mu, pat):
	mu = Partition(mu)
	pat = Partition(pat)
	r = mu.length()

	a = pat.length()
	b = pat.conjugate().length()

	
	R = range(0,r)
	for Y in itertools.combinations(R, a):
		nu = Partition([mu[i] for i in Y]).conjugate()

		c = nu.length()
		if c>= b:
			C = range(0,c)
			for X in itertools.combinations(C,b):
				nu2 = Partition([nu[i] for i in X]).conjugate()			

				if nu2 == pat:
					return false	

	return true

def GenAllPartitionsAvoiding(pat, N):
	L = []
	pat = Partition(pat)
	for mu in Partitions(N):
		if PartitionAvoids(mu,pat):
		 #if not IsSubsetPartition(pat,mu):
			L.append(mu)
	return L

def GenAllPartitionsContaining(pat, N):
	L=[]
	pat = Partition(pat)
	for mu in Partitions(N):
		if not PartitionAvoids(mu,pat):
			L.append(mu)
	return L	

def CountRangePartionsAvoiding(pat,N):
	return len(GenAllPartitionsAvoiding(pat,N))


def CountPartitionsContainingFixedTop(pat, numNewCols, order):
	top = pat[0]+numNewCols
	pat = Partition(pat)
	L=[]

	for n in range(sum(pat)+1, order+1):
		count = 0
		for mu in Partitions(n):
			if mu[0] == top:
				if not PartitionAvoids(mu,pat):
					count += 1
		L.append(count)
	return L	

		
def Parallel_Count(Pats, N,output):
	for pat in Pats:
		k = str(CountRangePartionsAvoiding(pat,N))
		#k = str(CountPartitionsContainingFixedTop(pat,1,N))
		output.put((pat,k))  

def GetWilfClasses(k,N, num_jobs):
	output = mp.Queue()
	AllPats = [p for p in Partitions(k)]
	Jobs = []
	n = floor(len(AllPats)/num_jobs)


	for i in range(0,num_jobs-1):
		Jobs.append(mp.Process(target=Parallel_Count, args=(AllPats[i*n:(i+1)*n], N,output)))

	Jobs.append(mp.Process(target=Parallel_Count, args=(AllPats[(i+1)*n:], N,output)))

	for job in Jobs:
		job.start()

	for job in Jobs:
		job.join()

	D = {}		
	while not output.empty():
		pat,k = output.get()
		if D.has_key(k):
			D[k].append(pat)
		else:
			D[k] = [pat]		
	
	return D


def CountAll(k,N):
	for pat in Partitions(k):
		L = [len(GenAllPartitionsAvoiding(pat,i)) for i in range(1,N+1)]
		print L,pat			


def GenAllAvoiding(S,n):
	P = [x for x in Partitions(n)]

	for pat in S:
		P0 = []
		for p in P: 
			if PartitionAvoids(p,pat):
				P0.append(p)
		P = P0

	return P	
				

def GetAvoidanceSequence(S, N):
	L = []
	for n in range(1,N+1):
		x = GenAllAvoiding(S,n)
		L.append(len(x))
	return L


def DistinctPartsSequences(n,N):
	for p in Partitions(n,max_slope = -1):
		print p, GetAvoidanceSequence([p],N)

# def GetAvoidanceSequence(S, N):
# 	L = []
# 	for n in range(1,N+1):
# 		x = GenAllPartitionsAvoiding(S,n)
# 		L.append(len(x))
# 	return L

	
def ClassTesting(n,N):

	Patterns = [x for x in Partitions(n)]

	D = {}
	for k in range(2,3):
		for S in itertools.combinations(Patterns,k):
			 key = str(GetAvoidanceSequence(S,N))

			 if key in D:
			 	D[key].append(S)
			 else:
			 	D[key] = [S]

	for key in D:
		print key
		print D[key]
		print 		 	

			

# Code for direct GF-------------------------------------

def InsertColumnsFromPartition(mu, add_sigma):
	L = list(Partition(mu).conjugate()) + list(add_sigma)
	L.sort()
	L.reverse()
	return list(Partition(L).conjugate())

def InsertColumnsFromPartition2(mu, cols):
	if len(mu)< len(cols):
		return "Error"

	L = list(mu)
	for r in range(0,len(cols)):	
		L[r] += cols[r]	
	return L

def InsertColumns(mu,num_cols):
	M = []
	mu = Partition(mu)
	l = len(mu)
	mu_conj = mu.conjugate()

	for w in range(num_cols,num_cols*l+1):
		for sigma in Partitions(w, length=num_cols):
			if sigma[0]<= l:
				x = mu_conj+list(sigma)
				
				x.sort()
				x.reverse()
				# Partition(T).conjugate(), sigma.conjugate()
				M.append( (Partition(x).conjugate(),sigma) )
	return M

def GetMeet2(P):
	l = max([x[0] for x in P])
	x = [0]*l
	for mu in P:
		e = Partition(mu).to_exp()
		for i in range(0,len(e)):
			x[i] = max(x[i],e[i])
	return Partition(exp = x)	

def ComputeGF(mu,numNewCols,order, printSeries):
	q = var('q')
	F = 0*q
	top = mu[0] + numNewCols

	M = [x[0] for x in InsertColumns(mu,numNewCols)]
	
	for i in range(1, len(M)+1):

		for x in itertools.combinations(M, i):
			F = F + (-1)**(i+1)*q**sum(GetMeet2(x))

	if printSeries:
		for i in range(1,top+1):
			F = F/(1-q**i)
		print  F.full_simplify().series(q,order)
	else:
		print  F.full_simplify()





# Code for Alternative description of GF-----------------

def GetAuxilliaryPairs(k,R):
	A = []
	for a in range(0,k+1):

		for n in range(0,R*a+1):
			for mu in Partitions(n,max_part=R,length = a):
					for m in range(0,(R+a)*(k-a)+1):
						for alpha in Partitions(m,max_part=R+a,length = k-a):
							
							if mu == []:
								A.append([mu,alpha])
							elif mu[-1] > 1:
								A.append([mu,alpha])

	return A					

def GetNormAuxPair(lamb,off,pat):
	b = len(off)

	s = 0
	for i in range(0,len(lamb)):
		x = lamb[i]
		s += pat[x-1] + i

	return sum(lamb)+sum(off) +s + sum(pat)

def DisplayAuxNorms(k,pat):
	R = len(pat)
	A = GetAuxilliaryPairs(k,R)

	for (mu,beta) in A:
		print mu,beta, GetNormAuxPair(mu,beta,pat)

def GetAuxPairs(numNewCols, height):
	AuxPairs=[]

	for lambdaConj_top in range(0,numNewCols+1):
		offsetConj_top = numNewCols - lambdaConj_top
		for lambConj in PartitionsInRectangleFixedTop(lambdaConj_top,height):
			lamb = lambConj.conjugate()
			if lamb == [] or lamb[-1] >1:
				for offConj in PartitionsInRectangleFixedTop(offsetConj_top,height+lambdaConj_top):
					off = offConj.conjugate()
					AuxPairs.append([lamb,off]) 
	return AuxPairs				

def ComputeGFUsingAux(pat, numNewCols,order, printSeries):
	q = var('q')
	F = 0*q

	top = pat[0] + numNewCols

	
	A = GetAuxPairs(numNewCols,len(pat))

	for (lamb,off) in A:
		
		w = GetNormAuxPair(lamb,off,pat)
		F += (-1)**len(lamb)*q**w

	

	if printSeries:
		for i in range(1,top+1):
			F = F/(1-q**i)
		return  F.full_simplify().series(q,order)
	else:
		return  F.full_simplify()

def DisplayAllMeetsSinglePattern(k,pat):
	D={}
	D2={}
	U = []
	h = len(pat)

	for insertWeight in range(1,k*h+1):
		for add_sigma in Partitions(insertWeight):
			if (add_sigma[0] <= h) and (len(add_sigma) == k):
				U.append(add_sigma)

	for n in range(1,12):
		for K in itertools.combinations(U,n):
			D[K] = []	

	for K in D.keys():
		M = [InsertColumnsFromPartition(pat,sig) for sig in K]
		D[K].append(GetMeet2(M))
		

	for K in D.keys():
		K2 = tuple(D[K])
		if D2.has_key(K2):
			D2[K2].append(K)
		else:
			D2[K2] = [K]			

	for k in D2.keys():
		L = list(D2[k])
		L.sort(key = lambda x: len(x))
		for x in L:
			print x

			# print x, max(i[0] for i in x),min(i[0] for i in x),"/",max(i[1] for i in x),min(i[1] for i in x)
		print 

def GenerateInvariantColSetsTopBottom(mu,sig):
	maxHeight = max(len(sig), len(mu))
	A = mu + [0]*(maxHeight+1-len(mu))
	B = sig + [0]*(maxHeight+1-len(sig))

	S = set()
	S.add(tuple(mu))
	S.add(tuple(sig))
	for i in range(0,maxHeight):
		if A[i] >= B[i+1]:
			S.add( tuple([x for x in A[:i+1] + B[i+1:] if x!= 0]) )

		if B[i] >= A[i+1]:
			S.add( tuple([x for x in B[:i+1] + A[i+1:] if x!= 0]) )

	L = list(S)
	L.sort(key = lambda x: len(x))

	return [list(x) for x in L]

def CheckIfEqual(A,B,C, patWeight):
	ColCombination1=[A,B]
	ColCombination2=[A,B,C]

	patHeight = max(len(A), len(B))+1
	
	for pat in Partitions(patWeight, length = patHeight):
			M1 = [InsertColumnsFromPartition2(pat,x) for x in ColCombination1]
			M2 = [InsertColumnsFromPartition2(pat,x) for x in ColCombination2]
			if GetMeet2(M1) != GetMeet2(M2):
				return false
	
	return true

def GenerateInvariantColSetsBruteForce(mu,sig,patWeight):
	A = mu
	B = sig

	h = max(len(A),len(B))
	ColCombination1=[A,B]

	patHeight = max(len(A), len(B))+1
	Pass = []

	for C in PartitionsInRectangle(max(A[0],B[0]),h):
		ColCombination2 = [A,B,C]
		Cworks = true
		for pat in Partitions(patWeight, length = patHeight):
			M1 = [InsertColumnsFromPartition2(pat,x) for x in ColCombination1]
			M2 = [InsertColumnsFromPartition2(pat,x) for x in ColCombination2]
			if GetMeet2(M1) != GetMeet2(M2):
				Cworks = false
				break
		if Cworks:
			Pass.append(C)	
	
	return Pass			

def DisplayAllMeets(k,h,maxPatWeight):
	D={}
	Clusters={}
	Columns = []

	for insertWeight in range(1,k*h+1):
		for x in Partitions(insertWeight, max_length = h):
			if (x[0] == k):
				Columns.append(x)

	for n in range(1,16):
		for ColCombination in itertools.combinations(Columns,n):
			D[ColCombination] = []	


	# for patWeight in range(h, maxPatWeight+1):
	for pat in Partitions(maxPatWeight, length = h):
		for ColCombination in D.keys():
			M = [InsertColumnsFromPartition2(pat,x) for x in ColCombination]

			D[ColCombination].append(GetMeet2(M))

	# for K in D.keys():
	# 	print D[K], K
		

	for K in D.keys():
		K2 = tuple(D[K])
		if Clusters.has_key(K2):
			Clusters[K2].append(K)
		else:
			Clusters[K2] = [K]			

	
	mySum = 0		
	for ClusterKey in Clusters.keys():
		even = 0
		odd = 0
		
		ACluster = list(Clusters[ClusterKey])
		ACluster.sort(key = lambda x: len(x))

		for SetOfPartitions in ACluster:
			if len(SetOfPartitions)%2 == 0:
				even +=1
			else:
				odd +=1 

			# MAX2 = max([NumberPartsOfSize(mu,2) for mu in SetOfPartitions])	
			# MAX0 = h-min([len(mu) for mu in SetOfPartitions])
			# print SetOfPartitions, MAX2, MAX0
			print SetOfPartitions
		print even, odd
		print 
			
		# 	if MAX2 == 3 and MAX0 == 3:
		# 		print SetOfPartitions

		# if MAX2 == 3 and MAX0 == 3:
		# 	mySum += 1
		# 	print 


	# print mySum


# TESTING ---------------------