Die Herausforderung ist denkbar einfach: Bei einer bestimmten Zahl teilen Sie die Ziffern in ein Array kleinerer Zahlen auf, sodass die resultierenden Zahlen nicht abnehmen. Der Haken ist, dass Sie es so aufteilen müssen, dass die Array-Länge maximal ist.

Verwirrt?

• Sie erhalten eine positive Ganzzahl über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument in einem beliebigen praktischen, eindeutigen Eingabeformat.
• Sie müssen die Dezimalstellen der Zahl in zusammenhängende, nicht zusammenhängende Gruppen unterteilen.
• Das durch diese Zifferngruppen dargestellte Zahlenfeld sollte sortiert werden (in der üblichen, nicht abnehmenden Reihenfolge), ohne die Gruppen neu anzuordnen .
• In Fällen, in denen mehr als eine solche Partition vorhanden ist, müssen Sie die Eingabe in so viele Zahlen wie möglich unterteilen. Geben Sie bei Gleichstand ein solches Ergebnis zurück.
• Sie können das Array an STDOUT (oder die nächstgelegene Alternative) oder als Funktionsrückgabewert ausgeben. Im Falle von STDOUT (oder der nächstgelegenen Alternative) sollte das Array in einem geeigneten, eindeutigen Listenformat gedruckt werden.
• Die aufgeteilten Zahlen sollten keine führenden Nullen haben. So kann zum Beispiel 1002003nicht als [1, 002, 003]oder gedruckt werden [1, 2, 3]und die einzig gültige Antwort ist [100, 2003].

Testfälle:

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]

Wertung

Das ist Code-Golf, also gewinnt der kürzeste Code in Bytes.

Pyth, 34

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

Probieren Sie es hier online aus . Beachten Sie, dass dies eine zeitliche (und räumliche) Komplexität von O (n) hat. Daher 12345678901234567890dauert der Testfall im Online-Compiler zu lange. Verwenden Sie stattdessen die Offline-Version (1 Minute auf meinem Laptop).

Dies ist nur mein erster Versuch. Möglicherweise gibt es Raum für Verbesserungen.

Zuerst einige Ideen, wie mein Algorithmus funktioniert.

• Ich interpretiere die Eingabe als String und nicht als Zahl.
• Dann erstelle ich alle möglichen Teilmengen von [0, 1, 2, ..., len(n-1)]
• Für jede dieser Untermengen (lasst uns nehmen [1, 4, 5]) teile ich die Eingabezeichenfolge unter Verwendung dieser Zahlen in Teile auf. [input[0:1], input[1, 4], input[4,5], input[5,len(input)]].
• Danach versuche ich, diese Zahlen in Strings umzuwandeln. Es kann zwei Probleme geben. Pyth (oder Python) löst eine Ausnahme für eine leere Zeichenfolge und für eine Zahlenfolge aus, die mit beginnt 0. Deshalb benutze ich einen try - catchBlock (eigentlich eine Endlosschleife mit einer sofortigen Unterbrechung). Wenn die Konvertierung erfolgreich war, füge ich das Ergebnis einer Liste hinzu Y.
• Nachdem ich alle Teilmengen verarbeitet habe, filtere ich die Liste Ynach Ergebnissen, die bereits sortiert sind, und drucke die letzte aus (die letzte hat die meisten Gruppen).

Nun die ausführliche Erklärung:

                            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)

Mathematica, 134 127 Bytes

Das ist ziemlich ineffizient, da es viel mehr Partitionen erzeugt als die gültigen. Der 324142434445Testfall läuft innerhalb weniger Sekunden, aber ich würde es nicht versuchen 12345678901234567890.

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

Dies definiert eine unbenannte Funktion, die eine Ganzzahl annimmt und eine Liste von Ganzzahlen zurückgibt.

Erläuterung

Die Lesereihenfolge dieses Codes ist ein wenig uneinheitlich, daher werde ich in der Reihenfolge aufteilen, in der er gelesen (und größtenteils ausgewertet) werden soll:

• d=IntegerDigits@#Holen Sie sich die Dezimalstellen der Eingabe und weisen Sie diese Liste zu d.

• SetPartitions(was erfordert Needs@"Combinatorica`";) gibt mir alle partitionen davon. Es gibt jedoch viel mehr zurück, als ich eigentlich möchte, da es die Eingabe als Menge behandelt . Das macht es ineffizient, aber ich benutze es, weil der kürzeste Weg, den ich kenne, um alle Listenpartitionen zu erhalten, viel länger ist. Wenn die Liste ein Beispiel wäre, würde {1, 2, 3}die Funktion Folgendes zurückgeben:

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

  Beachten Sie, dass a) die aufeinanderfolgenden Partitionen alle in der richtigen Reihenfolge sind und b) die Partitionen von grob nach fein sortiert sind.

• Select[...,...&] filtert diese Liste dann nach der anonymen Funktion, die als zweites Argument übergeben wird.
  • Join @@ # == d prüft, ob wir tatsächlich eine Listenpartition anstelle einer allgemein festgelegten Partition haben.
  • #~FreeQ~{0, __} Überprüft, dass keine Partition mit einer führenden Null beginnt.
  • 0 <= ## & @@ f /@ #ist ein bisschen dunkler. Zuerst ordnen wir FromDigitsjede Liste in der Partition zu, um die durch die Ziffern dargestellten Zahlen wiederzugewinnen. Dann wenden wir uns 0 <= ##diesen Zahlen zu, wobei ##sich auf alle Zahlen bezieht. Wenn es sich bei der Partition um eine handelt, {1, 23, 45}wird diese auf erweitert 0 <= 1 <= 23 <= 45, sodass überprüft wird, ob das Array sortiert ist.
• Last@gibt mir dann die letzte nach dem filtern übrig gebliebene partition - das funktioniert, weil SetPartitionsschon die partitionen so sortiert sind, dass die feinsten am ende sind.
• Zum Schluss werden f/@die Nummern aus den Ziffernlisten wiederhergestellt.

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>""]

Es ist ein bisschen chaotisch, aber na ja. Das Programm generiert nur alle gültigen Partitionen rekursiv. Der interessante Teil ist, dass alles, was notwendig war, um führende Nullen zu verbieten, eine zusätzliche or "1">s[i:]>""Bedingung war.

Nimmt Eingaben wie f("12345678901234567890")und gibt eine Liste von Ints zurück.

Pyth, 62 61 60

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

Erläuterung

Der Algorithmus generiert alle Binärzahlen zwischen 0(einschließlich) und 2^(n-1)(ausschließlich), wobei ndie Länge der Eingabe ist.

Die Binärziffern von jedem werden dann einem Trennzeichen ( N) für 1 und nichts für 0 zugeordnet.

Diese Zeichen werden dann zwischen die einzelnen Eingabezeichen eingefügt, und das Ergebnis wird durch geteilt N, um eine Liste zu erhalten.

Die Werte in den Listen werden dann in ganze Zahlen zerlegt und die Listen werden nach Länge sortiert. Dann müssen nur noch nicht sortierte und an führenden Nullen aufgeteilte herausgefiltert werden, wonach die längste Liste ausgewählt wird.

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

(NICHT-WETTBEWERBSFÄHIG) Pyth, 25 Bytes

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

Probieren Sie es online!

Wie es funktioniert:

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

J, 109 Bytes

Sehr lang, benötigt aber mindestens O (n * (2n)!) Speicher und O (n * log (n) * (2n)!) Zeit, wobei n die Länge der Eingabe ist. (Versuchen Sie also nicht, es mit mehr als 5 Ziffern auszuführen.)

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

Die Funktion nimmt die Eingabe als String.

Beispiele:

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

Methode:

• Fügen Sie der Eingabe die gleiche Anzahl von Leerzeichen wie die Länge hinzu.
• Permutiere es auf jede mögliche Weise.
• Überprüfen Sie, ob die raumlose Zeichenfolge mit der Eingabe identisch ist (dh eine Partition davon ist).
• Ersetzen Sie '0' durch '_1', um führende Nulllösungen ungültig zu machen.
• Bewerten Sie jede Zeichenfolge.
• Finde die längste Liste, die auch sortiert ist. Dies ist der Rückgabewert.

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]

Testlauf:

*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]

So funktioniert es: Die Hilfsfunktion fteilt die Eingabeliste in jede mögliche Liste von Unterlisten auf. gZuerst werden diejenigen mit einer Unterliste verworfen, die mit 0und dann diejenigen ohne die richtige Reihenfolge beginnen. Verbinde jede verbleibende Liste mit ihrer Länge, nimm das Maximum und verwerfe den Längenteil erneut.