Partition into increasing subsequences

Question

Specification

This challenge is simple to state: your input is a non-empty array of nonnegative integers, and your task is to partition it into as few increasing subsequences as possible. More formally, if the input array is A, then the output is an array of arrays B such that:

• Each arrays in B form a partition of A into disjoint (not necessarily contiguous) subsequences. Inductively, this means that either B is the singleton array containing A, or the first element of B is a subsequence of A and the rest form a partition of A with that subsequence removed.
• Every array in B is (not necessarily strictly) increasing.
• The number of arrays in B is minimal.

Both the input and output can be taken in the native array format of your language. Note that there may be several correct outputs.

Example

Consider the input array A = [1,2,1,2,5,4,7,1]. One possible output is B = [[1],[1,2,4,7],[1,2,5]]. The partition condition is evident from this diagram:

A    1 2 1 2 5 4 7 1
B[0]               1
B[1] 1 2       4 7
B[2]     1 2 5

Also, each array in B is increasing. Finally, A can't be split into two increasing subsequences, so the length of B is also minimal. Thus it's a valid output.

Rules and scoring

You can write a function or a full program. The lowest byte count wins, and standard loopholes are disallowed. There is no time bound, but you should evauate your solution on all test cases before submitting it.

Test cases

Only one possible output is shown, but there may be several valid options. In particular, the order of the arrays in the result doesn't matter (but each individual array should be in increasing order).

[0] -> [[0]]
[3,5,8] -> [[3,5,8]]
[2,2,2,2] -> [[2,2,2,2]]
[1154,1012,976,845] -> [[845],[976],[1012],[1154]]
[6,32,1,2,34,8] -> [[1,2,8],[6,32,34]]
[1,12,1,12,1,13] -> [[1,1,1,13],[12,12]]
[6,4,6,13,18,0,3] -> [[0,3],[4,6,13,18],[6]]
[1,2,3,2,3,4,7,1] -> [[1,1],[2,2,3,4,7],[3]]
[0,9,2,7,4,5,6,3,8] -> [[0,2,3,8],[4,5,6],[7],[9]]
[7,1,17,15,17,2,15,1,6] -> [[1,1,6],[2,15],[7,15,17],[17]]
[4,12,2,10,15,2,2,19,16,12] -> [[2,2,2,12],[4,10,15,16],[12,19]]
[10,13,9,2,11,1,10,17,19,1] -> [[1,1],[2,10,17,19],[9,11],[10,13]]
[3,7,3,8,14,16,19,15,16,2] -> [[2],[3,3,8,14,15,16],[7,16,19]]
[15,5,13,13,15,9,4,2,2,17] -> [[2,2,17],[4],[5,9],[13,13,15],[15]]

Answer 1

Haskell, 54 bytes

n#[]=[[n]]
n#(l:c)|[n]<=l=(n:l):c|1<2=l:n#c
foldr(#)[]

Usage example: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]-> [[2,2,2,12],[4,10,15,16],[12,19]]

How it works: go through the input list starting at the right end. Build the output list (of lists) by prepending the current element n to first sublist l where n is less or equal to the head of l. If there's none, make a new singleton list of n at the end of the output list.

Answer 2

Pyth, 20 bytes

fTu&ahfSI+THGHGQm[)Q

Try it online: Demonstration or Test Suite

Greedy approach. I create len(input) empty lists. Then I iterate over each number in the input an choose the first list, which is still sorted after appending the number.

Explanation:

fTu&ahfSI+THGHGQm[)Q   implicit: Q = input list
                m[)Q   create a list of empty lists and assign to G
  u            Q       iterate over all numbers H in input:
      f     G             filter for lists T in G, which satisfy:
         +TH                 create a new list out of T and H
       SI                    and check if it is sorted
     h                    take the first such list T
    a        H            and append H
   &          G           logical and with G (so that u doesn't overwrite G)
fT                     remove all empty lists