Partition en sous-séquences croissantes

16

spécification

Ce défi est simple à énoncer: votre entrée est un tableau non vide d'entiers non négatifs, et votre tâche consiste à le partitionner en aussi peu de sous-séquences croissantes que possible. Plus formellement, si le tableau d'entrée est A, alors la sortie est un tableau de tableaux Btel que:

  • Chaque tableau Bforme une partition de Asous-séquences disjointes (pas nécessairement contiguës). Inductivement, cela signifie que soit Ble tableau singleton contient A, soit le premier élément de Best une sous-séquence de Aet le reste forme une partition de Acette sous-séquence supprimée.
  • Chaque tableau en Baugmente (pas nécessairement strictement).
  • Le nombre de tableaux dans Best minimal.

L'entrée et la sortie peuvent être prises dans le format de tableau natif de votre langue. Notez qu'il peut y avoir plusieurs sorties correctes.

Exemple

Considérez le tableau d'entrée A = [1,2,1,2,5,4,7,1]. Une sortie possible est B = [[1],[1,2,4,7],[1,2,5]]. La condition de partition est évidente à partir de ce diagramme:

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

De plus, chaque tableau en Baugmente. Enfin, Ane peut pas être divisé en deux sous-séquences croissantes, donc la longueur de Best également minimale. C'est donc une sortie valide.

Règles et notation

Vous pouvez écrire une fonction ou un programme complet. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites. Il n'y a pas de limite de temps, mais vous devez évaluer votre solution sur tous les cas de test avant de la soumettre.

Cas de test

Une seule sortie possible est affichée, mais il peut y avoir plusieurs options valides. En particulier, l'ordre des tableaux dans le résultat n'a pas d'importance (mais chaque tableau individuel doit être en ordre croissant).

[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
la source
3
Les règles semblent autoriser des solutions telles que [0,5,2,0] -> [[0,5],[0,2]](c'est-à-dire recycler le premier zéro au lieu d'utiliser chacune d'elles une fois). Est-ce intentionnel?
feersum
@feersum Ce n'était pas intentionnel, bonne prise. J'ai réécrit les conditions B, j'espère qu'elles sont plus claires maintenant.
Zgarb

Réponses:

3

Haskell, 54 octets

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

Exemple d'utilisation: foldr(#)[] [4,12,2,10,15,2,2,19,16,12]->[[2,2,2,12],[4,10,15,16],[12,19]]

Comment ça marche: parcourez la liste de saisie en commençant à l'extrémité droite. Construisez la liste de sortie (des listes) en ajoutant l'élément courant nà la première sous-liste lnest inférieur ou égal à la tête de l. S'il n'y en a pas, créez une nouvelle liste singleton nà la fin de la liste de sortie.

nimi
la source
1

Pyth, 20 octets

fTu&ahfSI+THGHGQm[)Q

Essayez-le en ligne: démonstration ou suite de tests

Approche gourmande. Je crée len(input)des listes vides. Ensuite, j'itère sur chaque numéro de la inputliste et choisissez la première, qui est toujours triée après avoir ajouté le numéro.

Explication:

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
la source
@ThomasKwa A testé un grand nombre de cas de test supplémentaires maintenant. Impossible d'en trouver un seul, ce qui donne le mauvais résultat. Je suis sûr que Greedy renvoie toujours le bon résultat.
Jakube
@ThomasKwa Oh, ce contre-exemple était à une stratégie différente gourmande (trouver la sous-séquence augmentant le plus longtemps, la supprimer et recurse). Je n'arrive pas non plus à trouver un cas de test pour lequel cette soumission échoue ...
Zgarb
Eh bien, je pense qu'il incombe au répondeur de prouver que cela fonctionne. Je voterai positivement si cela s'avère valide.
lirtosiast