wpm · March 1, 2019 22:48 · Mar 1, 2019
diff --git a/maximal_fully_ordered_sublists.py b/maximal_fully_ordered_sublists.py
@@ -0,0 +1,47 @@
+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)))