15,665,718 members
See more:
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!
Posted