Revision history [back]

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.