CoCalc Public Filesresearch / partitions / IntegerPartitionPatterns.py
Author: Nathan McNew
Description: Partitions
1import itertools
2import copy
3import time,sys
4import multiprocessing as mp
5
6
7# code for Rook-equivalence
8
9def GetHiddenRows(mu):
10	h = len(mu)
11	H = []
12
13	for i in range(0,h):
14		if mu[h-i-1] > len(H):
15			H.append(h-1-i)
16	return H
17
18def GetMultiSetHiddenL(mu):
19	M = []
20	R = GetHiddenRows(mu)
21	for r in R:
22		M.append(r+mu[r])
23	return sorted(M)
24
25def GetRookClasses(n):
26	D={}
27	for mu in Partitions(n):
28		k = str(GetMultiSetHiddenL(mu))
29		if D.has_key(k):
30			D[k].append(mu)
31		else:
32			D[k] = [mu]
33	return D
34
35
36# code for Wilf-equivalence
37def NumberPartsOfSize(mu,k):
38	return len([p for p in list(mu) if p==k])
39
40def PartitionsInRectangleFixedTop(top,h):
41	P = []
42	if top ==0:
43		return [Partition([])]
44
45	for weight in range(top,top*h+1):
46		for mu in Partitions(weight, max_length = h):
47			if  mu[0] == top:
48				P.append(mu)
49
50	return P
51
52def PartitionAvoids(mu, pat):
53	mu = Partition(mu)
54	pat = Partition(pat)
55	r = mu.length()
56
57	a = pat.length()
58	b = pat.conjugate().length()
59
60
61	R = range(0,r)
62	for Y in itertools.combinations(R, a):
63		nu = Partition([mu[i] for i in Y]).conjugate()
64
65		c = nu.length()
66		if c>= b:
67			C = range(0,c)
68			for X in itertools.combinations(C,b):
69				nu2 = Partition([nu[i] for i in X]).conjugate()
70
71				if nu2 == pat:
72					return false
73
74	return true
75
76def GenAllPartitionsAvoiding(pat, N):
77	L = []
78	pat = Partition(pat)
79	for mu in Partitions(N):
80		if PartitionAvoids(mu,pat):
81		 #if not IsSubsetPartition(pat,mu):
82			L.append(mu)
83	return L
84
85def GenAllPartitionsContaining(pat, N):
86	L=[]
87	pat = Partition(pat)
88	for mu in Partitions(N):
89		if not PartitionAvoids(mu,pat):
90			L.append(mu)
91	return L
92
93def CountRangePartionsAvoiding(pat,N):
94	return len(GenAllPartitionsAvoiding(pat,N))
95
96
97def CountPartitionsContainingFixedTop(pat, numNewCols, order):
98	top = pat[0]+numNewCols
99	pat = Partition(pat)
100	L=[]
101
102	for n in range(sum(pat)+1, order+1):
103		count = 0
104		for mu in Partitions(n):
105			if mu[0] == top:
106				if not PartitionAvoids(mu,pat):
107					count += 1
108		L.append(count)
109	return L
110
111
112def Parallel_Count(Pats, N,output):
113	for pat in Pats:
114		k = str(CountRangePartionsAvoiding(pat,N))
115		#k = str(CountPartitionsContainingFixedTop(pat,1,N))
116		output.put((pat,k))
117
118def GetWilfClasses(k,N, num_jobs):
119	output = mp.Queue()
120	AllPats = [p for p in Partitions(k)]
121	Jobs = []
122	n = floor(len(AllPats)/num_jobs)
123
124
125	for i in range(0,num_jobs-1):
126		Jobs.append(mp.Process(target=Parallel_Count, args=(AllPats[i*n:(i+1)*n], N,output)))
127
128	Jobs.append(mp.Process(target=Parallel_Count, args=(AllPats[(i+1)*n:], N,output)))
129
130	for job in Jobs:
131		job.start()
132
133	for job in Jobs:
134		job.join()
135
136	D = {}
137	while not output.empty():
138		pat,k = output.get()
139		if D.has_key(k):
140			D[k].append(pat)
141		else:
142			D[k] = [pat]
143
144	return D
145
146
147def CountAll(k,N):
148	for pat in Partitions(k):
149		L = [len(GenAllPartitionsAvoiding(pat,i)) for i in range(1,N+1)]
150		print L,pat
151
152
153def GenAllAvoiding(S,n):
154	P = [x for x in Partitions(n)]
155
156	for pat in S:
157		P0 = []
158		for p in P:
159			if PartitionAvoids(p,pat):
160				P0.append(p)
161		P = P0
162
163	return P
164
165
166def GetAvoidanceSequence(S, N):
167	L = []
168	for n in range(1,N+1):
169		x = GenAllAvoiding(S,n)
170		L.append(len(x))
171	return L
172
173
174def DistinctPartsSequences(n,N):
175	for p in Partitions(n,max_slope = -1):
176		print p, GetAvoidanceSequence([p],N)
177
178# def GetAvoidanceSequence(S, N):
179# 	L = []
180# 	for n in range(1,N+1):
181# 		x = GenAllPartitionsAvoiding(S,n)
182# 		L.append(len(x))
183# 	return L
184
185
186def ClassTesting(n,N):
187
188	Patterns = [x for x in Partitions(n)]
189
190	D = {}
191	for k in range(2,3):
192		for S in itertools.combinations(Patterns,k):
193			 key = str(GetAvoidanceSequence(S,N))
194
195			 if key in D:
196			 	D[key].append(S)
197			 else:
198			 	D[key] = [S]
199
200	for key in D:
201		print key
202		print D[key]
203		print
204
205
206
207# Code for direct GF-------------------------------------
208
210	L = list(Partition(mu).conjugate()) + list(add_sigma)
211	L.sort()
212	L.reverse()
213	return list(Partition(L).conjugate())
214
215def InsertColumnsFromPartition2(mu, cols):
216	if len(mu)< len(cols):
217		return "Error"
218
219	L = list(mu)
220	for r in range(0,len(cols)):
221		L[r] += cols[r]
222	return L
223
224def InsertColumns(mu,num_cols):
225	M = []
226	mu = Partition(mu)
227	l = len(mu)
228	mu_conj = mu.conjugate()
229
230	for w in range(num_cols,num_cols*l+1):
231		for sigma in Partitions(w, length=num_cols):
232			if sigma[0]<= l:
233				x = mu_conj+list(sigma)
234
235				x.sort()
236				x.reverse()
237				# Partition(T).conjugate(), sigma.conjugate()
238				M.append( (Partition(x).conjugate(),sigma) )
239	return M
240
241def GetMeet2(P):
242	l = max([x[0] for x in P])
243	x = [0]*l
244	for mu in P:
245		e = Partition(mu).to_exp()
246		for i in range(0,len(e)):
247			x[i] = max(x[i],e[i])
248	return Partition(exp = x)
249
250def ComputeGF(mu,numNewCols,order, printSeries):
251	q = var('q')
252	F = 0*q
253	top = mu[0] + numNewCols
254
255	M = [x[0] for x in InsertColumns(mu,numNewCols)]
256
257	for i in range(1, len(M)+1):
258
259		for x in itertools.combinations(M, i):
260			F = F + (-1)**(i+1)*q**sum(GetMeet2(x))
261
262	if printSeries:
263		for i in range(1,top+1):
264			F = F/(1-q**i)
265		print  F.full_simplify().series(q,order)
266	else:
267		print  F.full_simplify()
268
269
270
271
272
273# Code for Alternative description of GF-----------------
274
275def GetAuxilliaryPairs(k,R):
276	A = []
277	for a in range(0,k+1):
278
279		for n in range(0,R*a+1):
280			for mu in Partitions(n,max_part=R,length = a):
281					for m in range(0,(R+a)*(k-a)+1):
282						for alpha in Partitions(m,max_part=R+a,length = k-a):
283
284							if mu == []:
285								A.append([mu,alpha])
286							elif mu[-1] > 1:
287								A.append([mu,alpha])
288
289	return A
290
291def GetNormAuxPair(lamb,off,pat):
292	b = len(off)
293
294	s = 0
295	for i in range(0,len(lamb)):
296		x = lamb[i]
297		s += pat[x-1] + i
298
299	return sum(lamb)+sum(off) +s + sum(pat)
300
301def DisplayAuxNorms(k,pat):
302	R = len(pat)
303	A = GetAuxilliaryPairs(k,R)
304
305	for (mu,beta) in A:
306		print mu,beta, GetNormAuxPair(mu,beta,pat)
307
308def GetAuxPairs(numNewCols, height):
309	AuxPairs=[]
310
311	for lambdaConj_top in range(0,numNewCols+1):
312		offsetConj_top = numNewCols - lambdaConj_top
313		for lambConj in PartitionsInRectangleFixedTop(lambdaConj_top,height):
314			lamb = lambConj.conjugate()
315			if lamb == [] or lamb[-1] >1:
316				for offConj in PartitionsInRectangleFixedTop(offsetConj_top,height+lambdaConj_top):
317					off = offConj.conjugate()
318					AuxPairs.append([lamb,off])
319	return AuxPairs
320
321def ComputeGFUsingAux(pat, numNewCols,order, printSeries):
322	q = var('q')
323	F = 0*q
324
325	top = pat[0] + numNewCols
326
327
328	A = GetAuxPairs(numNewCols,len(pat))
329
330	for (lamb,off) in A:
331
332		w = GetNormAuxPair(lamb,off,pat)
333		F += (-1)**len(lamb)*q**w
334
335
336
337	if printSeries:
338		for i in range(1,top+1):
339			F = F/(1-q**i)
340		return  F.full_simplify().series(q,order)
341	else:
342		return  F.full_simplify()
343
344def DisplayAllMeetsSinglePattern(k,pat):
345	D={}
346	D2={}
347	U = []
348	h = len(pat)
349
350	for insertWeight in range(1,k*h+1):
354
355	for n in range(1,12):
356		for K in itertools.combinations(U,n):
357			D[K] = []
358
359	for K in D.keys():
360		M = [InsertColumnsFromPartition(pat,sig) for sig in K]
361		D[K].append(GetMeet2(M))
362
363
364	for K in D.keys():
365		K2 = tuple(D[K])
366		if D2.has_key(K2):
367			D2[K2].append(K)
368		else:
369			D2[K2] = [K]
370
371	for k in D2.keys():
372		L = list(D2[k])
373		L.sort(key = lambda x: len(x))
374		for x in L:
375			print x
376
377			# 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)
378		print
379
380def GenerateInvariantColSetsTopBottom(mu,sig):
381	maxHeight = max(len(sig), len(mu))
382	A = mu + [0]*(maxHeight+1-len(mu))
383	B = sig + [0]*(maxHeight+1-len(sig))
384
385	S = set()
388	for i in range(0,maxHeight):
389		if A[i] >= B[i+1]:
390			S.add( tuple([x for x in A[:i+1] + B[i+1:] if x!= 0]) )
391
392		if B[i] >= A[i+1]:
393			S.add( tuple([x for x in B[:i+1] + A[i+1:] if x!= 0]) )
394
395	L = list(S)
396	L.sort(key = lambda x: len(x))
397
398	return [list(x) for x in L]
399
400def CheckIfEqual(A,B,C, patWeight):
401	ColCombination1=[A,B]
402	ColCombination2=[A,B,C]
403
404	patHeight = max(len(A), len(B))+1
405
406	for pat in Partitions(patWeight, length = patHeight):
407			M1 = [InsertColumnsFromPartition2(pat,x) for x in ColCombination1]
408			M2 = [InsertColumnsFromPartition2(pat,x) for x in ColCombination2]
409			if GetMeet2(M1) != GetMeet2(M2):
410				return false
411
412	return true
413
414def GenerateInvariantColSetsBruteForce(mu,sig,patWeight):
415	A = mu
416	B = sig
417
418	h = max(len(A),len(B))
419	ColCombination1=[A,B]
420
421	patHeight = max(len(A), len(B))+1
422	Pass = []
423
424	for C in PartitionsInRectangle(max(A[0],B[0]),h):
425		ColCombination2 = [A,B,C]
426		Cworks = true
427		for pat in Partitions(patWeight, length = patHeight):
428			M1 = [InsertColumnsFromPartition2(pat,x) for x in ColCombination1]
429			M2 = [InsertColumnsFromPartition2(pat,x) for x in ColCombination2]
430			if GetMeet2(M1) != GetMeet2(M2):
431				Cworks = false
432				break
433		if Cworks:
434			Pass.append(C)
435
436	return Pass
437
438def DisplayAllMeets(k,h,maxPatWeight):
439	D={}
440	Clusters={}
441	Columns = []
442
443	for insertWeight in range(1,k*h+1):
444		for x in Partitions(insertWeight, max_length = h):
445			if (x[0] == k):
446				Columns.append(x)
447
448	for n in range(1,16):
449		for ColCombination in itertools.combinations(Columns,n):
450			D[ColCombination] = []
451
452
453	# for patWeight in range(h, maxPatWeight+1):
454	for pat in Partitions(maxPatWeight, length = h):
455		for ColCombination in D.keys():
456			M = [InsertColumnsFromPartition2(pat,x) for x in ColCombination]
457
458			D[ColCombination].append(GetMeet2(M))
459
460	# for K in D.keys():
461	# 	print D[K], K
462
463
464	for K in D.keys():
465		K2 = tuple(D[K])
466		if Clusters.has_key(K2):
467			Clusters[K2].append(K)
468		else:
469			Clusters[K2] = [K]
470
471
472	mySum = 0
473	for ClusterKey in Clusters.keys():
474		even = 0
475		odd = 0
476
477		ACluster = list(Clusters[ClusterKey])
478		ACluster.sort(key = lambda x: len(x))
479
480		for SetOfPartitions in ACluster:
481			if len(SetOfPartitions)%2 == 0:
482				even +=1
483			else:
484				odd +=1
485
486			# MAX2 = max([NumberPartsOfSize(mu,2) for mu in SetOfPartitions])
487			# MAX0 = h-min([len(mu) for mu in SetOfPartitions])
488			# print SetOfPartitions, MAX2, MAX0
489			print SetOfPartitions
490		print even, odd
491		print
492
493		# 	if MAX2 == 3 and MAX0 == 3:
494		# 		print SetOfPartitions
495
496		# if MAX2 == 3 and MAX0 == 3:
497		# 	mySum += 1
498		# 	print
499
500
501	# print mySum
502
503
504# TESTING ---------------------
505