Sorted Lexical Partition of a Number

Question

The challenge is really simple: given a number, you split its digits into an array of smaller numbers such that the resulting numbers are non-decreasing. The catch is that you have to split it such that the array length is maximal.

Confused?

• You are given a positive integer via STDIN (or closest alternative), command-line argument or function argument in any convenient, unambiguous input format.
• You have to partition the number's decimal digits into contiguous, disjoint groups.
• The array of numbers represented by these digit groups should be sorted (in the usual, non-decreasing order) without rearranging the groups.
• In cases where more than one such partition exists, you have to partition the input into as many numbers as possible. In the case of ties, return one such result.
• You can output the array to STDOUT (or closest alternative) or as a function return value. In case of STDOUT (or closest alternative), the array should be printed in any convenient, unambiguous list format.
• The split numbers should not have leading zeroes. So for instance 1002003 cannot be printed as either [1, 002, 003] or [1, 2, 3] and the only valid answer for it is [100, 2003].

Test cases:

123456 -> [1, 2, 3, 4, 5, 6]
345823 -> [3, 4, 5, 8, 23]
12345678901234567890 -> [1, 2, 3, 4, 5, 6, 7, 8, 90, 123, 456, 7890]
102 -> [102]
302 -> [302]
324142 -> [3, 24, 142] OR [32, 41, 42]
324142434445 -> [32, 41, 42, 43, 44, 45]
1356531 -> [1, 3, 5, 6, 531]
11121111111 -> [1, 1, 1, 2, 11, 11, 111]
100202003 -> [100, 202003]

Scoring

This is code-golf so shortest code in bytes wins.

Answer 1

Pyth, 34

FNyUz#aYmv:zhdedC,+0N+NlzB)efqSTTY

Try it online here. Notice, this has a time (and space) complexity of O(n). Therefore the test case 12345678901234567890 takes too long in the online compiler. Use the offline one instead (1 minute on my laptop).

This is only my first attempt. There might be some room for improvements.

First some ideas how my algorithm works.

• I interpret the input as string and not as a number.
• Then I create all possible subsets of [0, 1, 2, ..., len(n-1)]
• For each of these subsets (lets take [1, 4, 5]), I split the input string into part using these numbers. [input[0:1], input[1, 4], input[4,5], input[5,len(input)]].
• Afterwards I try to convert these numbers into strings. There can be two problems. Pyth (or Python) throws an exception for an empty string, and for a string of numbers starting with 0. Therefore I use a try - catch block (actually infinity loop with an immediate break). If converting was successfully, I add the result to a list Y.
• After I handled all subsets, I filter the list Y for results, that are already sorted and print the last one (the last one has the most groups).

Now the detailed explanation:

                            Implicit: z = input() (z is a String!)
                                      Y = empty list
FNyUz                       for each subset N of [0, 1, 2, ..., len(z)-1]:

     #                         start try-catch block (actually an infinite loop, 
                               but the Python implementation uses a try catch. 

      aY                          append to Y:
                C,+0N+Nlz            zip([0] + N, N + [len(z)])
        m                            map each element d to
          :zhded                     z[d[0]:d[-1]]
         v                           evaluated
                         B        if this didn't throw an exception already, end the infinite loop
                          ) end for loop   

 f    Y      filter Y for elements T, for which
  qSTT           sorted(T) == T
e            and print the last one (the subsets generated with yUz are sorted 
             by length, so the last one has the most groups)

Answer 2

Mathematica, 134 127 bytes

This is pretty inefficient since it generates a lot more partitions than the valid ones. The 324142434445 test case runs within a few seconds, but I wouldn't try 12345678901234567890.

f/@Last@Select[Needs@"Combinatorica`";f=FromDigits;SetPartitions[d=IntegerDigits@#],0<=##&@@f/@#&&Join@@#==d&&#~FreeQ~{0,__}&]&

This defines an unnamed function which takes an integer and returns a list of integers.

Explanation

The reading order of this code is a bit all over the place, so I'll break down in the order it's intended to be read (and evaluated for the most part):

• d=IntegerDigits@# get the decimal digits of the input and assign this list to d.

• SetPartitions (which requires Needs@"Combinatorica`";) gives me all partitions of this. However, it returns a lot more than I actually want since it treats the input as a set. This is what makes it inefficient, but I'm using this because the shortest way I know to get all list partitions is much longer. As an example, if the list was {1, 2, 3} the function would return:

  {{{1, 2, 3}}, {{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 3}, {2}}, {{1}, {2}, {3}}}
  

  Note that a) the consecutive partitions are all in the right order and b) the partitions are sorted from coarsest to finest.

• Select[...,...&] then filters this list by the anonymous function passed in as the second argument.
  • Join @@ # == d checks that we've actually got a list partition instead of a general set partition.
  • #~FreeQ~{0, __} checks that no partition starts with a leading zero.
  • 0 <= ## & @@ f /@ # is a bit more obscure. First we map FromDigits onto each list in the partition to recover the numbers represented by the digits. Then we apply 0 <= ## to those numbers, where ## refers to all the numbers. If the partition is {1, 23, 45} then this expands to 0 <= 1 <= 23 <= 45, so it checks that the array is sorted.
• Last@ then gives me the last partition left after filtering - this works because SetPartitions already sorted the partitions, such that the finest ones are at the end.
• Finally, f/@ recovers the numbers from the digit lists.

Answer 3

Python 3, 134 bytes

def f(s,n=0,L=[],R=[],i=0):
 while s[i:]:i+=1;m=int(s[:i]);R=max([f(s[i:],m,L+[m]),R][m<n or"1">s[i:]>"":],key=len)
 return[L,R][s>""]

It's a little messy, but oh well. The program just generates all valid partitions recursively. The interesting part is that to disallow leading zeroes, all that was necessary was an additional or "1">s[i:]>"" condition.

Takes input like f("12345678901234567890") and returns a list of ints.

Answer 4

Pyth, 62 61 60

JlzKkef&qJsml`dTqTSTolNmmibTcjKsC,z+m>Ndt>+*J]0jk2_JKNU^2-J1

Explanation

The algorithm works by generating all binary numbers between 0 (inclusive) and 2^(n-1) (exclusive), where n is the length of the input.

The binary digits of each are then mapped to a separator (N) for 1 and nothing for 0.

These characters are then inserted between each input character, and the result is split by N, yielding a list.

The values in the lists are then parsed to integers, and the lists are sorted by length. Then all that is left is to filter out non-sorted ones and ones that have been split at leading zeroes, after which the longest list is picked.

Jlz                                                   set J to len(input)
Kk                                                    set K to ""
e                                                     take the last of:
 f&                                                    only take lists where:
   qJsml`dT                                             sum of string lengths of items
                                                        is equal to length of input and
           qTST                                         list is in order
               olN                                       sort by length
                  m                                       map k over...
                   mibT                                    convert items to int (base-10)
                       c                        N           split by N
                        jK                                   join by ""
                          s                                   sum to combine tuples
                           C,z                                 zip input with
                              +                K                append [""] for equal lengths
                               m>Nd                              replace 1 with N, 0 with ""
                                   t                              take all but first
                                    >        _J                    take len(input) last values
                                     +                              pad front of binary with
                                      *J]0                           [0] times input's length
                                          jk2                        current k in binary
                                                 U^2-J1  range 0..2^(len(input)-1)-1

Answer 5

(NON-COMPETING) Pyth, 25 bytes

ef&&Fmnhd\0T.A<V=NsMTtN./

Try it online!

How it works:

ef&&Fmnhd\0T.A<V=NsMTtN./  Q = eval(input())
                         ./  all partitions of Q
 f                       ./  filter all partitions of Q where:
  &                            both:
   &Fmnhd\0T                     neither substring starts with "0"
                               and:
            .A<V=NsMTtN          all entries are less than their proceeding ones
e                            returns the last amongst the filtered partitions

Answer 6

J, 109 bytes

Very long but at least takes up O(n * (2n)!) memory and O(n * log(n) * (2n)!) time where n is the length of the input. (So don't try to run it with more than 5 digits.)

f=.3 :0
>({~(i.>./)@:(((-:/:~)@(#$])*#)@>))<@".(' 0';' _1')rplc"1~(#~y-:"1' '-."#:~])(i.!2*#y)A.y,' '#~#y
)

The function takes the input as a string.

Examples:

   f every '5423';'103';'1023'
  5 423
103   0
 10  23

Method:

• Add the same number of spaces to the input as it's length.
• Permute it in every possible way.
• Check if the spaceless string is the same as the input (i.e. it's a partition of it).
• Replace ' 0's to ' _1's to invalidate leading zero solutions.
• Evaluate each string.
• Find the longest list which is also sorted. This is the return value.

Answer 7

Haskell, 161 bytes

(#)=map
f[x]=[[[x]]]
f(h:t)=([h]:)#f t++(\(a:b)->(h:a):b)#f t
g l=snd$maximum[(length x,x::[Int])|x<-[read#y|y<-f l,all((/='0').head)y],and$zipWith(>=)=<<tail$x]

Test run:

*Main> mapM_ (print . g) ["123456","345823","12345678901234567890","102","302","324142","324142434445","1356531","11121111111","100202003"]
[1,2,3,4,5,6]
[3,4,5,8,23]
[1,2,3,4,5,6,7,8,90,123,456,7890]
[102]
[302]
[32,41,42]
[32,41,42,43,44,45]
[1,3,5,6,531]
[1,1,1,2,11,11,111]
[100,202003]

How it works: the helper function f splits the input list into every possible list of sublists. g first discards those with a sublist beginning with 0 and then those without the proper order. Pair every remaining list with it's length, take the maximum and discard the length part again.