Let $T$ be a tableau, for example [[1,3,5],[2,4,6]]. I want to find all tuples of lists of size 3 such that the content of the tuple is the same as the content of $T$, which is ${1,2,3,4,5,6}$ (the content can be a multi-set). In this example, all the tuples are (each line is a tuple which have the content {1,2,3,4,5,6})
[((1, 2, 3), (4, 5, 6)),
((1, 2, 4), (3, 5, 6)),
((1, 2, 6), (3, 4, 5)),
((1, 4, 5), (2, 3, 6)),
((1, 5, 6), (2, 3, 4))]
I made a program as follows.
import itertools
def ListAToN(a,n):
r=[]
for i in range(a,n+1):
r.append(i)
return r
def SetDifference(A,B): # A-B
r=[]
for i in A:
if (i in B)==False:
r.append(i)
return r
def ContentOfTableauWithMultiplicities(l): # l is tableau
r=[]
for i in l:
for j in i:
r.append(j)
r=sorted(r)
return r
def IsNonCrossing(I1,J1): # I1,J1 have the same size
k=len(I1)
I2=sorted(I1)
J2=sorted(J1)
r=1
for a in ListAToN(0,k-1):
for b in ListAToN(a+1,k-1):
t1=[]
for i in ListAToN(a,b):
t1.append(I2[i])
t2=[]
for j in ListAToN(a,b):
t2.append(J2[j])
t3=[]
for i in ListAToN(a+1,b-1):
t3.append(I2[i])
t4=[]
for j in ListAToN(a+1,b-1):
t4.append(J2[j])
if IsWeaklySeparated(t1,t2)==0 and set(t3)==set(t4):
return(0)
return r
def IsIncreasingOrdered(l): # is there j such that l_j<...<l_n<l_1<...<l_{j-1}
r=1
n=len(l)
for j in ListAToN(0,n-2):
if l[j]>l[j+1]:
r=0
break
return r
def IsWeaklySeparated(I1,J1): # I1,J1 have the same size
r1=sorted(SetDifference(I1,J1))
r2=sorted(SetDifference(J1,I1))
if r1==[] and r2==[]:
r=1
else:
#print(r1,r2)
if min(r1)<min(r2):
c1=r1
c2=r2
else:
c1=r2
c2=r1
r=0
for i in ListAToN(0,len(c1)-1):
t1=[]
for j in ListAToN(0,i):
t1.append(c1[j])
t1=t1+c2
for j in ListAToN(i+1,len(c1)-1):
t1.append(c1[j])
if IsIncreasingOrdered(t1)==1:
r=1
break
return r
def IsNonCrossingList(l): # I1,J1 have the same size
r=1
if len(l)>=2:
for i in itertools.combinations(l, 2):
if IsNonCrossing(i[0],i[1])==0:
r=0
return r
return r
def NonCrossingTupleWithSameContentAsT(T): # T = [[1,2,3,5,8],[2,3,4,8,9]] is a tableau
r=[]
if T != []:
k=len(T[0])
m=len(T) # number of columns of T
n=0
for i in T:
if n<max(i):
n=max(i)
for i in itertools.combinations_with_replacement(itertools.combinations(ListAToN(1,n),k), m):
if ContentOfTableauWithMultiplicities(i)==ContentOfTableauWithMultiplicities(T) and IsNonCrossingList(i)==1:
r.append(i)
return r
NonCrossingTupleWithSameContentAsT([[1,3,5,7],[2,4,6,8]])
One problem is that in the function NonCrossingTupleWithSameContentAsT, I need to use a loop
for i in itertools.combinations_with_replacement(itertools.combinations(ListAToN(1,n),k), m):
if ContentOfTableauWithMultiplicities(i)==ContentOfTableauWithMultiplicities(T) and IsNonCrossingList(i)==1:
r.append(i)
which may take a long time if the given tableau has large entry, for example
NonCrossingTupleWithSameContentAsT([[1,3,5,20],[2,4,6,30],[3,8,9,33]])
takes a very long time to run. On the other hand, there are only 12 numbers in [[1,3,5,20],[2,4,6,30],[3,8,9,33]]. Is there some other method to find all non-crossing tuples which have the content ${ 1,2,3,3,4,5,6,8,9,20,30,33 }$? Thank you very much.
