CoCalc Public Filesresearch / partitions / IntegerPartitionPatterns.pyOpen in CoCalc with one click!
Author: Nathan McNew
Description: Partitions
1
import itertools
2
import copy
3
import time,sys
4
import multiprocessing as mp
5
6
7
# code for Rook-equivalence
8
9
def 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
18
def GetMultiSetHiddenL(mu):
19
M = []
20
R = GetHiddenRows(mu)
21
for r in R:
22
M.append(r+mu[r])
23
return sorted(M)
24
25
def 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
37
def NumberPartsOfSize(mu,k):
38
return len([p for p in list(mu) if p==k])
39
40
def 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
52
def 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
76
def 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
85
def 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
93
def CountRangePartionsAvoiding(pat,N):
94
return len(GenAllPartitionsAvoiding(pat,N))
95
96
97
def 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
112
def 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
118
def 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
147
def 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
153
def 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
166
def 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
174
def 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
186
def 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
209
def InsertColumnsFromPartition(mu, add_sigma):
210
L = list(Partition(mu).conjugate()) + list(add_sigma)
211
L.sort()
212
L.reverse()
213
return list(Partition(L).conjugate())
214
215
def 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
224
def 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
241
def 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
250
def 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
275
def 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
291
def 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
301
def 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
308
def 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
321
def 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
344
def DisplayAllMeetsSinglePattern(k,pat):
345
D={}
346
D2={}
347
U = []
348
h = len(pat)
349
350
for insertWeight in range(1,k*h+1):
351
for add_sigma in Partitions(insertWeight):
352
if (add_sigma[0] <= h) and (len(add_sigma) == k):
353
U.append(add_sigma)
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
380
def 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()
386
S.add(tuple(mu))
387
S.add(tuple(sig))
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
400
def 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
414
def 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
438
def 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