16
\$\begingroup\$

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]]
\$\endgroup\$
  • 3
    \$\begingroup\$ The rules seem to allow solutions like [0,5,2,0] -> [[0,5],[0,2]] (i.e., recycling the first zero instead of using each of them once). Is that intentional? \$\endgroup\$ – feersum Dec 7 '15 at 5:28
  • \$\begingroup\$ @feersum That wasn't intentional, good catch. I've rewritten the conditions for B, hopefully they're clearer now. \$\endgroup\$ – Zgarb Dec 7 '15 at 15:39
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ @ThomasKwa Tested quite a lot of additional test-cases now. Couldn't find a single one, that gives the wrong result. I'm quite sure, that Greedy always returns the correct result. \$\endgroup\$ – Jakube Dec 7 '15 at 22:38
  • \$\begingroup\$ @ThomasKwa Oh, that counterexample was to a different greedy strategy (find the longest increasing subsequence, remove it and recurse). I also can't seem to find a test case for which this submission fails... \$\endgroup\$ – Zgarb Dec 8 '15 at 4:23
  • \$\begingroup\$ Well, I think the burden is on the answerer to prove it works. I'll upvote if this is proven valid. \$\endgroup\$ – lirtosiast Dec 8 '15 at 4:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.