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)))