Maximal Fully-Ordered Sublists

maximal_fully_ordered_sublists.py

def maximal_fully_ordered_sublists(s: List[T]) -> List[List[T]]:
    """
    Find maximum-length sequences of in-order items in a list.

    Let s be a list of items over which there exists a total ordering defined by the < operator.
    Let a fully-ordered sublist s' of s be s with elements removed so that the elements of s' are monotonically
    increasing.
    The maximal fully-ordered sublists of s are the set of fully-ordered sublists such that no sublist is contained in
    another one.

    For example, given the list (R, S, T, A, B, U, V) with alphabetic ordering, the fully-ordered sublists would be

        R, S, T, U, V
        A, B, U, V

    :param s: list of items
    :return: maximal fully-ordered sublists of s in order from longest to shortest
    """
    # Build a topologically sorted DAG between the items of s in which the edge a -> b can only exist if b comes after
    # a in s.
    if not s:
        return [s]
    s = sorted(enumerate(s), key=itemgetter(1))
    g = {s[-1][1]: None}
    agenda = []
    for x, y in sliding_window(2, s):
        remaining_agenda = []
        agenda.insert(0, x)
        while agenda:
            z = agenda.pop(0)
            if z[0] < y[0]:
                g[z[1]] = y[1]
            else:
                g[z[1]] = None
                remaining_agenda.insert(0, z)
        agenda = remaining_agenda.copy()
    # Find all the paths in the DAG starting at nodes that have no predecessors.
    paths = []
    minima = set(g.keys()) - set(g.values())
    for x in minima:
        path = []
        while x is not None:
            path.append(x)
            x = g[x]
        paths.append(path)
    # Sort these paths from largest to smallest. (And then in lexicographic order to break ties.)
    return sorted(paths, key=lambda p: (-len(p), tuple(p)))