15,611,036 members

See more:

Let T be a semistandard Young tableau of rectangular shape. For example,

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,

**What I have tried:**

I have a program which works. But I would like to make it faster.

We can test the program by

But it takes very long time in larger example. For example,

Do you know how to make the program faster? Thank you very much!

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

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!

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