#VATTERPLUS.txt: One of the  Maple packages accompanying the article
#Counting Permutations that Avoid Many Patterns
#By Yonah BIERS-ARIEL, Haripriya CHAKRABORTY, John CHIARELLI, Bryan EK, Andrew LOHR, Jinyoung PARK, 
#Justin SEMONSEN, Richard VOEPEL, Mingjia YANG, Anthony ZALESKI, and Doron ZEILBERGER 
#http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/pamp.html

with(combinat):
print(`Please read in VATTER.txt to fully utilize this file.`):

read `VATTER.txt`:

Help:=proc()
	print(`VatterR3S4(r,s,K,Gvul:=4,GvulGap:=2), PermR3S4(r,s), VatterR4S5(r,s,K,Gvul:=4,GvulGap:=2), PermR4S5(r,s), redu(L), IV(n,k), IsBad1(pi,p), SimplifyPatterns(P)`):
end:

#############################################################################################################################
#Initially created by Anthony Zaleski. Edited by Bryan Ek.
#############################################################################################################################
#PermR3S4(r,s): returns a set of r random permutations of length 3, and s random permutations of length 4.
#Makes sure that no 4 permutation is a child of a 3 permutation.
PermR3S4:=proc(r,s) local a,i:
	a:={}:
	while nops(a)<>r+s do
		a:=SimplifyPatterns({seq(randperm(3),i=1..r),seq(randperm(4),i=1..s)}):
	od:
	a:
end:

#VatterR3S4(r,s,K,Gvul:=4,GvulGap:=2): runs SchemeFast from VATTER.txt
#on PermR3S4 K times, and prints the sets and their enumeration schemes.
#Gvul and GvulGap are optional search parameters for SchemeFast.
VatterR4S5:=proc(r,s,K,Gvul:=4,GvulGap:=2) local k,S,V,s1,co,st:
	st:=time():
	S:={seq(PermR3S4(r,s),k=1..K)}:#The size of S may actually be <K due to randomly picking the same permutation set.
	while nops(S)<K do#This while loop ensures we will actually consider K DIFFERENT permutation sets.
		S:=S union {seq(PermR3S4(r,s),k=nops(S)+1..K)}:
	od:
	#This might not be desired. We can actually consider picking each permutation set independently.
	#Oh, but then a specific “find” or “fail” is not counted the correct number of times.
	#This doesn’t appear to take too much extra time.
	#Presuming K is not too large, this will be able to finish. Might want to put in a check to ensure we can find K different sets.
	co:=0:
	print(``): print(``):
	print(`ENUMERATION SCHEMES OF PERMUTATIONS AVOIDING`,r,`PATTERNS OF LENGTH 3 AND`,s,`PATTERNS OF LENGTH 4`):
	print(``): print(``):
	for s1 in S do
		V:=SchemeFast(s1,Gvul,GvulGap):
		if V[1]<>FAIL then
			co:=co+1:
			print(`Theorem`,co):
			print(`The enumeration scheme of permutations avoiding`):
			print(s1):#Shall we include the set of patterns avoided by the reversing bijection?
			print(`is `):
			print(V):
			print(``):
			S:=S minus {s1}:
		fi:
	od:
	print(``):
	print(`The computation took `,time()-st,`seconds.`):
	print(`SchemeFast failed for the following `,nops(S),` sets:`):
	S:
end:


#############################################################################################################################
#Adapted by Bryan Ek from work by Anthony Zaleski.
#############################################################################################################################
#PermR4S5(r,s): returns a set of r random permutations of length 4, and s random permutations of length 5.
#Makes sure that no 5 permutation is a child of a 4 permutation.
PermR4S5:=proc(r,s) local a,i:
	a:={}:
	while nops(a)<>r+s do
		a:=SimplifyPatterns({seq(randperm(4),i=1..r),seq(randperm(5),i=1..s)}):
	od:
	a:
end:

#VatterR4S5(r,s,K,Gvul:=4,GvulGap:=2): runs SchemeFast from VATTER.txt
#on PermR4S5 K times, and prints the sets and their enumeration schemes.
#Gvul and GvulGap are optional search parameters for SchemeFast.
VatterR4S5:=proc(r,s,K,Gvul:=4,GvulGap:=2) local k,S,V,s1,co,st:
	st:=time():
	S:={seq(PermR4S5(r,s),k=1..K)}:#The size of S may actually be <K due to randomly picking the same permutation set.
	while nops(S)<K do#This while loop ensures we will actually consider K DIFFERENT permutation sets.
		S:=S union {seq(PermR4S5(r,s),k=nops(S)+1..K)}:
	od:
	#This might not be desired. We can actually consider picking each permutation set independently.
	#Oh, but then a specific “find” or “fail” is not counted the correct number of times.
	#This doesn’t appear to take too much extra time.
	#Presuming K is not too large, this will be able to finish. Might want to put in a check to ensure we can find K different sets.
	co:=0:
	print(``): print(``):
	print(`ENUMERATION SCHEMES OF PERMUTATIONS AVOIDING`,r,`PATTERNS OF LENGTH 4 AND`,s,`PATTERNS OF LENGTH 5`):
	print(``): print(``):
	for s1 in S do
		V:=SchemeFast(s1,Gvul,GvulGap):
		if V[1]<>FAIL then
			co:=co+1:
			print(`Theorem`,co):
			print(`The enumeration scheme of permutations avoiding`):
			print(s1):#Shall we include the set of patterns avoided by the reversing bijection?
			print(`is `):
			print(V):
			print(``):
			S:=S minus {s1}:
		fi:
	od:
	print(``):
	print(`The computation took `,time()-st,`seconds.`):
	print(`SchemeFast failed for the following `,nops(S),` sets:`):
	S:
end:


#############################################################################################################################
#Work by Bryan Ek from Dr. Zeilberger’s Experimental Math Course Fall 2016. Some is duplicated in VATTER.txt.
#############################################################################################################################
#Inputs a list of numbers, and outputs the reduction as a permutation of nops(L).
#e.g. redu([e,pi,gamma,phi,h])=[4,5,2,3,1].
redu:=proc(L) local M,i,j:
	sort(sort(L,output=permutation),output=permutation):
end:
#IV(n,k): the set of increasing vectors of length k in {1,..,n}.
IV:=proc(n,k):
	{op(choose([seq(i,i=1..n)],k))}:
end:
#IsBad1(pi,p): inputs a permutation pi and a pattern p.
#Outputs true iff pi contains the pattern p
IsBad1:=proc(pi,p) local s:
	for s in IV(nops(pi),nops(p)) do
		if redu(pi[s])=p then
			return(true):
		fi:
	od:
	false:
end:
#SimplifyPatterns(P): inputs a set of patterns and outputs the reduced version.
#Removes all patterns that are children of others.
#P will be sorted by length of patterns.
SimplifyPatterns:=proc(P) local newP,i,j:
	newP:=P:
	for i from 1 to nops(P)-1 do
		for j from i+1 to nops(P) do
			if IsBad1(P[j],P[i]) then
				newP:=newP minus {P[j]}:
			fi:
		od:
	od:
	newP:
end: