2
\$\begingroup\$

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 the paper (The the non-crossing property has been programmed below).

Explicitly, non-crossing property is defined as follows:

Given two k-element subsets I and J of {1, \ldots, n}, denote by min(J) the minimal element in J and by max(I) the maximal element in I, we write I < J if max(I)<min(J). The sets I and J are called weakly separated if at least one of the following two conditions holds:

J-I can be partitioned into a disjoint union J-I = J' \sqcup J'' so that J' < I-J < J'';

I-J can be partitioned into a disjoint union I-J = I' \sqcup I'' so that I' < J-I < I''.

A pair I={i_1< \ldots < i_k}, J={j_1<\ldots<j_k} of k-element subsets of [n] is said to be non-crossing if for each 1 \le a < b \le k, either the pair {i_a, i_{a+1}, \ldots, i_b}, {j_a, j_{a+1}, \ldots, j_b} is weakly separated, or {i_{a+1}, \ldots, i_{b-1}} \ne {j_{a+1}, \ldots, j_{b-1}}.

An m-tuple (a_1, \ldots, a_m), each a_i is a sorted list, is called non-crossing m-tuple if any two a_i, a_j (i \ne j) are non-crossing.

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]].

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 flatten(l): 
    return [item for sublist in l for item in sublist]

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?

\$\endgroup\$
4
  • \$\begingroup\$ The function flatten() is missing. \$\endgroup\$
    – RootTwo
    Aug 21, 2022 at 23:17
  • \$\begingroup\$ @RootTwo, thank you very much! Sorry I forgot that I used SageMath so flatten is built in. We can define it as def flatten(l): return [item for sublist in l for item in sublist] I added it. \$\endgroup\$ Aug 22, 2022 at 6:11
  • \$\begingroup\$ Please provide more examples and a clear definition of what 'non-crossing tuple' means. Links to external resources are discouraged as they might be deleted. \$\endgroup\$
    – Marc
    Aug 22, 2022 at 19:29
  • \$\begingroup\$ @Marc, thanks for your suggestions! I added the definition of non-crossing tuple. \$\endgroup\$ Aug 23, 2022 at 13:29

1 Answer 1

1
\$\begingroup\$

First, a general review, then a speedier solution.

Numpy is imported, but doesn't appear to be used.

PEP-8 is the recommended (not required) style guide for python code. It includes suggestions for placement of import statements, name formatting, whitespace, etc. Whatever style you chose, be consistent. Your naming style does not seem consistent: some functions start with an uppercase letter, others with a lower case letter. Same with variable names.

m doesn't appear to be used in NonCrossingTupleWithSameContentAsT()

Choose meaningful variable names. When you look at your code in 6 months, will you remember what I and J are?

As of Python 3.7, the implementation of dict remembers the order if insertion of elements. Counter is a subclass of dict, so the keys are in insertion order as well. Math operations on Counters maintain the order. If the population is sorted, itertools.combinations() produces results in order as well. So, some of the sorting calls can be eliminated.

In IsNonCrossing() it may make sense to break out of the inner loop whenever I[a+1:b] != J[a+1:b].

If you add some code to NonCrossingTupleWithSameContentAsT to count and print the number of iterations of the loop, and the length of r, before and after duplicates are removed, you will find for the second example, that there are

1074900 candidates generated,
  26460 non-crossing candidates, and
    236 unique non-crossing candidates.

That's a lot of extra work.

In general, generating all possible combinations and filtering the results will be slow, except for small problems. The key is to try to only generate unique valid combinations. This can be done by modifying candidates() to check each tuple before adding it to a candidate to ensure it is non-crossing to each of the previous tuples and also not smaller than any of the previous tuples in the candidate.

With the modified candidates, my computer generates the results in about 0.25 seconds compared to 22.5 seconds for the original code.

Lastly, we can cache calls to is_noncrossing(). That reduces the time to about 0.125 seconds. A roughly 150:1 speedup.

import itertools 
import functools

from collections import Counter

def flatten(l): 
    return [item for sublist in l for item in sublist]

def noncrossing_tuples(T): 
    if T and T[0]:
        return list(candidates(Counter(sorted(flatten(T))), len(T[0])))

    else:
        return []

def candidates(content, k, candidate=()): 
    if len(content) < k:
        if len(content) == 0 and candidate:
            yield candidate
        else:
            return
        
    for I in itertools.combinations(content, k):
        # tuples in candidate are in non-decreaseing order
        if candidate and I < candidate[-1]:
            continue
            
        # new tuple is non-crossing with the other tuples
        if all(is_noncrossing(I, J) for J in candidate):
            yield from candidates(content - Counter(I), k, candidate + (I,))
     

@functools.cache
def is_noncrossing(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 is_weakly_separated(I[a:b+1], J[a:b+1])):
                return False

    return True
                
def is_weakly_separated(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 r1[0] >= r2[0]:
        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]

Note, I haven't tested the code extensively. For the two test cases it returns the same results as yours, without checking for duplicates. But I have a nagging feeling that there may be cases where it generates duplicate candidates. So it might be wise to still check for them.

\$\endgroup\$
1
  • \$\begingroup\$ thank you very much for your excellent answer and helpful suggestions! \$\endgroup\$ Aug 23, 2022 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.