Ask Your Question
0

Find all non-crossing tuples which have the same content as a given tableau.

asked 2022-07-15 09:02:39 +0100

lijr07 gravatar image

Let $T$ be a tableau, for example [[1,3,5],[2,4,6]]. I want to find all tuples of lists of size 3 such that the content of the tuple is the same as the content of $T$, which is ${1,2,3,4,5,6}$ (the content can be a multi-set). In this example, all the tuples are (each line is a tuple which have the content {1,2,3,4,5,6})

[((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))]

I made a program as follows.

import itertools

def ListAToN(a,n):
    r=[]
    for i in range(a,n+1):
        r.append(i)
    return r

def SetDifference(A,B): # A-B
    r=[]
    for i in A:
        if (i in B)==False:
            r.append(i)
    return r 

def ContentOfTableauWithMultiplicities(l): # l is tableau
    r=[]
    for i in l:
        for j in i:
            r.append(j)
    r=sorted(r)
    return r

def IsNonCrossing(I1,J1): # I1,J1 have the same size
    k=len(I1)
    I2=sorted(I1)
    J2=sorted(J1)
    r=1
    for a in ListAToN(0,k-1):
        for b in ListAToN(a+1,k-1):
            t1=[]
            for i in ListAToN(a,b):
                t1.append(I2[i])
            t2=[]
            for j in ListAToN(a,b):
                t2.append(J2[j])
            t3=[]
            for i in ListAToN(a+1,b-1):
                t3.append(I2[i])
            t4=[]
            for j in ListAToN(a+1,b-1):
                t4.append(J2[j])


            if IsWeaklySeparated(t1,t2)==0 and set(t3)==set(t4):
                return(0)
    return r 


def IsIncreasingOrdered(l): # is there j such that l_j<...<l_n<l_1<...<l_{j-1}


    r=1
    n=len(l)
    for j in ListAToN(0,n-2):
        if l[j]>l[j+1]:
            r=0
            break

    return r 


def IsWeaklySeparated(I1,J1): # I1,J1 have the same size


    r1=sorted(SetDifference(I1,J1))
    r2=sorted(SetDifference(J1,I1))

    if r1==[] and r2==[]:
        r=1
    else:
        #print(r1,r2)
        if min(r1)<min(r2):
            c1=r1
            c2=r2
        else: 
            c1=r2
            c2=r1 

        r=0

        for i in ListAToN(0,len(c1)-1):
            t1=[]
            for j in ListAToN(0,i):
                t1.append(c1[j])

            t1=t1+c2
            for j in ListAToN(i+1,len(c1)-1):
                t1.append(c1[j])

            if IsIncreasingOrdered(t1)==1:
                r=1
                break



    return r 

def IsNonCrossingList(l): # I1,J1 have the same size

    r=1
    if len(l)>=2:
        for i in itertools.combinations(l, 2):
            if IsNonCrossing(i[0],i[1])==0:
                r=0
                return r

    return r 

def NonCrossingTupleWithSameContentAsT(T): # T = [[1,2,3,5,8],[2,3,4,8,9]] is a tableau
    r=[]
    if T != []:
        k=len(T[0])
        m=len(T) # number of columns of T
        n=0
        for i in T:
            if n<max(i):
                n=max(i)

    for i in itertools.combinations_with_replacement(itertools.combinations(ListAToN(1,n),k), m):
        if ContentOfTableauWithMultiplicities(i)==ContentOfTableauWithMultiplicities(T) and IsNonCrossingList(i)==1:
            r.append(i)


    return r

NonCrossingTupleWithSameContentAsT([[1,3,5,7],[2,4,6,8]])

One problem is that in the function NonCrossingTupleWithSameContentAsT, I need to use a loop

for i in itertools.combinations_with_replacement(itertools.combinations(ListAToN(1,n),k), m):
        if ContentOfTableauWithMultiplicities(i)==ContentOfTableauWithMultiplicities(T) and IsNonCrossingList(i)==1:
            r.append(i)

which may take a long time if the given tableau has large entry, for example

NonCrossingTupleWithSameContentAsT([[1,3,5,20],[2,4,6,30],[3,8,9,33]])

takes a very long time to run. On the other hand, there are only 12 numbers in [[1,3,5,20],[2,4,6,30],[3,8,9,33]]. Is there some other method to find all non-crossing tuples which have the content ${ 1,2,3,3,4,5,6,8,9,20,30,33 }$? Thank you very much.

edit retag flag offensive close merge delete

Comments

What "non-crossing" means here? Following the standard definition for sets, tuples like ((1, 2, 4), (3, 5, 6)) that you listed would be crossing.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-07-15 18:30:42 +0100 )edit

@max, thanks for your comments. I used the definition in https://arxiv.org/pdf/2106.07142.pdf, Definition 1.8. Maybe the definitions are different.

lijr07 gravatar imagelijr07 ( 2022-07-15 20:34:43 +0100 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2022-07-15 14:15:07 +0100

Consider the following code. The key is method candidates which yields all m-tuples of k-tuples from the elements of input T. It takes as input a Counter with the multiplicity of each element in T. It's running time is independent from the values of the elements. Also, it ensures that the elements of a k-tuple are sorted, and so we can avoid sorting repeatedly k-tuples. However, it may yield multiple times a same m-tuple.

import itertools
from collections import Counter

def is_weakly_separated(I, J):
    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

    # Search for an index i such that list r1[:i+1] + r2 + r1[i+1:] is sorted
    for i in range(len(r1) - 1):
        if r2[0] < r1[i+1]:
            # We check if list r1[:i+1] + r2 + r1[i+1:] is ordered
            return r2[-1] <= r1[i+1]

    # It remains to check if list r1 + r2 is ordered
    return r1[-1] <= r2[0]

def is_non_crossing(I, J):
    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_non_crossing_list(L):
    return all(is_non_crossing(I, J) for I, J in itertools.combinations(L, 2))

def candidates(content, k, m):
    """
    Iterator over the m-tuples of k elements from content.

    With this implementation, elements are not repeated in a same tuple.

    INPUT:

    - ``content`` -- a ``Counter`` associated to each possible element it's
      multiplicity

    - ``k`` -- number of elements per tuple

    - ``m`` -- requested number of tuples
    """
    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, m - 1):
                yield T + L

def non_crossing_tuples_with_same_content(T):
    """
    Iterator over the non crossing tuples with same content as 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))

    # Unfortunately, we need to record yielded solutions to avoid duplicates
    seen = set()

    for c in candidates(Counter(content), k, m):
        if is_non_crossing_list(c):
            t = tuple(sorted(c))
            if t not in seen:
                yield t
                seen.add(t)

We can check that we get the same results than you.

sage: T = [[1,3,5],[2,4,6]]
sage: %time NonCrossingTupleWithSameContentAsT(T)
CPU times: user 1.68 ms, sys: 73 µs, total: 1.76 ms
Wall time: 1.82 ms
[((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))]
sage: %time list(non_crossing_tuples_with_same_content(T))
CPU times: user 669 µs, sys: 1e+03 ns, total: 670 µs
Wall time: 675 µs
[((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))]

and also

sage: T = [[1,3,5,7],[2,4,6,8]]
sage: %time Y = NonCrossingTupleWithSameContentAsT(T)
CPU times: user 14.7 ms, sys: 542 µs, total: 15.2 ms
Wall time: 15.3 ms
sage: %time L = list(non_crossing_tuples_with_same_content(T))
CPU times: user 2.46 ms, sys: 25 µs, total: 2.49 ms
Wall time: 2.52 ms
sage: Y == L
True

Since the new method is way faster, we can quickly get the result even if some elements have (very) large values

sage: T = [[1,3,5,20],[2,4,6,30],[3,8,9,33]]
sage: %time L = list(non_crossing_tuples_with_same_content(T))
CPU times: user 258 ms, sys: 3.31 ms, total: 262 ms
Wall time: 263 ms
sage: len(L)
210
sage: L[0]
((1, 2, 3, 4), (3, 5, 6, 8), (9, 20, 30, 33))
sage: L[1]
((1, 2, 3, 4), (3, 5, 6, 9), (8, 20, 30, 33))
sage: T = [[1,3,5,20],[2,4,6,30],[3,8,9,33333]]
sage: %time L = list(non_crossing_tuples_with_same_content(T))
CPU times: user 262 ms, sys: 3.31 ms, total: 265 ms
Wall time: 266 ms

We can certainly optimize further the code. For instance, method is_weakly_separated should consider only the first and last elements of I and J as other elements are equal.

edit flag offensive delete link more

Comments

@david, thank you very much for your excellent answer!

lijr07 gravatar imagelijr07 ( 2022-07-15 18:28:11 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-07-15 09:02:39 +0100

Seen: 181 times

Last updated: Jul 15 '22