Aufteilung in zunehmende Teilfolgen

16

Spezifikation

Diese Herausforderung ist einfach zu formulieren: Ihre Eingabe ist ein nicht leeres Array nichtnegativer Ganzzahlen, und Ihre Aufgabe besteht darin, es in möglichst wenige aufsteigende Teilsequenzen zu unterteilen. Genauer gesagt, wenn das Eingabearray ist A, ist die Ausgabe ein Array von Arrays, Bso dass:

  • Jedes Array Bbildet eine Aufteilung Ain nicht zusammenhängende (nicht notwendigerweise zusammenhängende) Teilfolgen. Induktiv bedeutet dies, dass entweder Bdas Singleton-Array enthalten Aist oder das erste Element Beine Teilfolge von ist Aund der Rest eine Partition von bildet, Awobei diese Teilfolge entfernt ist.
  • Jedes Array in Bnimmt (nicht unbedingt streng) zu.
  • Die Anzahl der Arrays Bist minimal.

Sowohl die Eingabe als auch die Ausgabe können im nativen Array-Format Ihrer Sprache erfolgen. Beachten Sie, dass es möglicherweise mehrere korrekte Ausgaben gibt.

Beispiel

Betrachten Sie das Eingabearray A = [1,2,1,2,5,4,7,1]. Eine mögliche Ausgabe ist B = [[1],[1,2,4,7],[1,2,5]]. Die Partitionsbedingung ist aus diesem Diagramm ersichtlich:

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

Außerdem nimmt jedes Array in Bzu. Lässt Asich schließlich nicht in zwei aufsteigende Teilfolgen aufteilen, so Bist auch die Länge minimal. Somit ist es eine gültige Ausgabe.

Regeln und Wertung

Sie können eine Funktion oder ein vollständiges Programm schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig. Es gibt keine Zeitbeschränkung, aber Sie sollten Ihre Lösung in allen Testfällen bewerten, bevor Sie sie einreichen.

Testfälle

Es wird nur eine mögliche Ausgabe angezeigt, es können jedoch mehrere gültige Optionen vorhanden sein. Insbesondere spielt die Reihenfolge der Arrays im Ergebnis keine Rolle (aber jedes einzelne Array sollte in aufsteigender Reihenfolge sein).

[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]]
Zgarb
quelle
3
Die Regeln scheinen Lösungen wie die [0,5,2,0] -> [[0,5],[0,2]]Wiederverwertung der ersten Null zuzulassen , anstatt sie jeweils einmal zu verwenden. Ist das beabsichtigt?
Feersum
@feersum Das war nicht beabsichtigt, guter Fang. Ich habe die Bedingungen für umgeschrieben B, hoffentlich sind sie jetzt klarer.
Zgarb,

Antworten:

3

Haskell, 54 Bytes

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

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

So funktioniert es: Gehen Sie die Eingabeliste beginnend am rechten Ende durch. Erstellen Sie die Ausgabeliste (von Listen), indem Sie das aktuelle Element nder ersten Unterliste voranstellen, lin nder der Kopf von kleiner oder gleich ist l. Wenn es keine gibt, erstellen Sie eine neue Singleton-Liste nam Ende der Ausgabeliste.

nimi
quelle
1

Pyth, 20 Bytes

fTu&ahfSI+THGHGQm[)Q

Probieren Sie es online aus: Demo oder Test Suite

Gieriger Ansatz. Ich erstelle len(input)leere Listen. Dann iteriere ich über jede Nummer in der und inputwähle die erste Liste aus, die nach dem Anhängen der Nummer noch sortiert ist.

Erläuterung:

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
Jakube
quelle
@ThomasKwa Viele zusätzliche Testfälle wurden jetzt getestet. Konnte keinen einzigen finden, der das falsche Ergebnis liefert. Ich bin mir ziemlich sicher, dass Greedy immer das richtige Ergebnis liefert.
Jakube
@ThomasKwa Oh, das Gegenbeispiel war eine andere gierige Strategie (finde die am längsten zunehmende Teilsequenz, entferne sie und rekursiere). Ich kann auch keinen Testfall finden, für den diese Einreichung fehlschlägt ...
Zgarb
Nun, ich denke, die Last liegt beim Antwortenden, um zu beweisen, dass es funktioniert. Ich stimme zu, wenn dies als gültig erwiesen ist.
Lirtosiast