Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900