CoCalc Shared Filesresearch / partitions / PartitionAvoidanceGF.py
Author: Nathan McNew
Description: Partitions
1# Brute force code for avoidance sequences
2import itertools
3def PartitionAvoids(mu, pat):
4	mu = Partition(mu)
5	pat = Partition(pat)
6	r = mu.length()
7
8	a = pat.length()
9	b = pat.conjugate().length()
10
11
12	R = range(0,r)
13	for Y in itertools.combinations(R, a):
14		nu = Partition([mu[i] for i in Y]).conjugate()
15
16		c = nu.length()
17		if c>= b:
18			C = range(0,c)
19			for X in itertools.combinations(C,b):
20				nu2 = Partition([nu[i] for i in X]).conjugate()
21
22				if nu2 == pat:
23					return false
24
25	return true
26
27def GenAllAvoiding(pat,n):
28	P = []
29	for p in Partitions(n):
30		if PartitionAvoids(p,pat):
31			P.append(p)
32	return P
33
34def GetAvoidanceSequence(pat, N):
35	L = []
36	for n in range(1,N+1):
37		x = GenAllAvoiding(pat,n)
38		L.append(len(x))
39	return L
40
41
42
43#Generating function code for avoidance sequences
44def GetExp(monomial):
45	if monomial == 1:
46		return 0
47	else:
48		return floor(log(monomial)(x=e))
49
50def GFTree(L, t):
51
52	if L != []:
53		if L[0] == 'E':
54			G = (GFTree(L[1:],1) - x*t*GFTree(L[1:],x*t))/(1-x*t)
55			return G.full_simplify()
56		else:
57			if t!= 0:
58				m = GetExp(t)
59				G = 0
60				F0 = GFTree(L[1:], 0)
61				for i in range(0,m+1):
62					G += GFTree(L[1:],x**i) - F0
63
64				G = 1/(1-x**(m+1))*G + F0
65				return G.full_simplify()
66			else:
67				return GFTree(L[1:], 0)
68
69	else:
70		return x*t/(1-x*t)
71
72
73def GetBoundaryDirections(mu):
74	B = []
75
76	B = B+ ['E']*(mu[-1]-1)
77	B += ['NE']
78
79
80	for i in range(len(mu)-2,0,-1):
81		k = (mu[i]-mu[i+1]-1)
82		B +=['E']*k
83		B += ['NE']
84
85	B +=['E']*((mu[0]-mu[1]-2))
86
87
88	B.reverse()
89
90	return B
91
92
93# Nathan the procedure "Test" is what you need to run this.
94# mu must be a partition (as a list) of a super distinct partition
95# N is the the number of terms you will see in the GF
96def Test(mu,N):
97	L = GetBoundaryDirections(mu)
98	print L
99	F = GFTree(L,1)
100	print F.full_simplify()
101
102	#print GetAvoidanceSequence(mu, N)
103	return F.series(x,N+1).coefficients(sparse = False)[1:]
104
105
106
107
108
109
110
111
112
113# def Get(N, k):
114# 	Seq = []
115# 	for n in range(1,N+1):
116# 		c = 0
117
118# 		for p in Partitions(n):
119# 			S = set()
120# 			for x in p:
121# 				S.add(x)
122# 			L = list(S)
123# 			L.sort()
124# 			if len(L) <=k and L[-1]- L[0]<= k-1:
125# 				c+=1
126
127# 		Seq.append(c)
128# 	return Seq
129
130# def GetTau_GF(N):
131# 	x,t = var('x,t')
132# 	T = x*0
133
134# 	for n in range(1,N+1):
135# 		for d in divisors(n):
136# 			T+=  t**d * x**n
137
138# 	return T.collect(x)
139
140# def PartitionsDifferBy_GF(N,K):
141# 	x,t = var('x,t')
142# 	F0 = GetTau_GF(N)
143
144# 	Fk = (F0(t=1) - F0(t=x*t)) / (1-x*t)
145
146
147
148# 	for k in range(2,K+1):
149# 		Fk = (Fk(t=1) - x*t*Fk(t=x*t)) / (1-x*t)
150
151
152# 	return Fk(t=1).series(x,N)
153
154
155# def CountGeneralizedDivisionAlgorithm_GF(N,K):
156# 	x = var('x')
157# 	F = x**K/(1-x**K)/(1-x**K)
158
159# 	for s in range(1,K):
160# 		F += x**s/(1-x**s) * 1/(1-x**K)
161
162# 	return F.series(x,N+1).coefficients(sparse = False)[1:]
163
164
165# def CountGeneralizedDivisionAlgorithm_Force(n,k):
166# 	c = 0
167# 	for a in range(1,n+1):
168# 		for r in range(0,a):
169# 			if n-k*r >= a:
170# 				if (n-k*r) % a == 0:
171# 					c +=1
172# 					# print n, a, (n-k*r)/a, r
173# 	return c
174
175# def GetSequence_Force(N,k):
176# 	L = []
177# 	for n in range(1,N+1):
178# 		L.append(CountGeneralizedDivisionAlgorithm_Force(n,k))
179# 	return L
180
181
182
183
184