Let T be a semistandard Young tableau of rectangular shape. For example,
[[1,2,4],[3,5,6]]
is such a tableau, where [1,2,4] and [3,5,6] are columns. All non-crossing tuples with the same content as T are
[((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))]
For example, (1,2,3), (4,5,6) are non-crossing in the sense of Definition 1.8 of page 9 of
https://arxiv.org/pdf/2106.07142.pdf[
^]
I have programmed the non-crossing property below.
Moreover,
((1, 2, 3), (4, 5, 6))
has content [1,2,3,4,5,6] which is the same as the content of
[[1,2,4],[3,5,6]]
.
What I have tried:
I have a program which works. But I would like to make it faster.
from numpy import array
from collections import Counter
import itertools
def NonCrossingTupleWithSameContentAsT(T):
if not T or not T[0]:
return []
k = len(T[0])
m = len(T) # number of columns of T
content = sorted(flatten(T))
r=[]
for c in candidates(Counter(content), k):
if IsNonCrossingList(c):
r.append(tuple(sorted(c)))
r=removeDuplicatesListOfLists(r)
return r
def candidates(content, k):
m=sum(content.values())/k
if len(content) < k:
return
for I in itertools.combinations(content, k):
# We ensure that elements inside a k-tuple are sorted
T = (tuple(sorted(I)), )
if m == 1:
yield T
else:
for L in candidates(content - Counter(I), k):
yield T + L
def IsNonCrossing(I,J): # I,J have the same size
k = len(I)
for a in range(k - 1):
for b in range(a + 1, k):
if (I[a+1:b] == J[a+1:b] and
not IsWeaklySeparated(I[a:b+1], J[a:b+1])):
return False
return True
def IsNonCrossingList(L):
return all(IsNonCrossing(I, J) for I, J in itertools.combinations(L, 2))
def IsWeaklySeparated(I,J): # I,J have the same size
r1 = sorted(set(I).difference(J))
r2 = sorted(set(J).difference(I))
if not r1 or not r2:
return True
if min(r1) >= min(r2):
r1, r2 = r2, r1
for i in range(len(r1) - 1):
if r2[0] < r1[i+1]:
return r2[-1] <= r1[i+1]
return r1[-1] <= r2[0]
def removeDuplicatesListOfLists(l):
l.sort()
r=list(l for l,_ in itertools.groupby(l))
return r
We can test the program by
r1=[[1,2,4],[3,5,6]]
%time r3=list(NonCrossingTupleWithSameContentAsT(r1))
r3
But it takes very long time in larger example. For example,
r1=[[1, 3, 6], [1, 3, 7], [2, 4, 7], [2, 4, 9], [5, 8, 9]]
%time r3=list(NonCrossingTupleWithSameContentAsT(r1))
r3
Do you know how to make the program faster? Thank you very much!