Tri par ordre aléatoire

Le tri aléatoire par blocs est une méthode (plutôt artificielle) de tri d'une liste. Il fonctionne comme suit, illustré par un exemple.

[6, 1, 0, 3, 2, 4, -2, -1]
                            Break list into contiguous blocks
[6][1, 0][3, 2, 4][-2, -1]
                            Sort each block
[6][0, 1][2, 3, 4][-2, -1]
                            Sort blocks lexicographically
[-2, -1][0, 1][2, 3, 4][6]
                            Concatenate
[-2, -1, 0, 1, 2, 3, 4, 6]

La partition en blocs contigus peut être choisie arbitrairement. Cependant, tous les choix de blocs ne produiront pas une liste triée à la fin:

[6, 1, 0, 3, 2, 4, -2, -1]
[6, 1, 0][3, 2, 4][-2, -1]
[0, 1, 6][2, 3, 4][-2, -1]
[-2, -1][0, 1, 6][2, 3, 4]
[-2, -1, 0, 1, 6, 2, 3, 4]

Si tous les blocs ont une longueur 1, ou s'il n'y a qu'un seul bloc, le résultat sera bien sûr trié. Mais ce sont des cas assez extrêmes. Dans ce défi, votre tâche consiste à trouver un équilibre entre le nombre de blocs et la longueur maximale d'un bloc.

La tâche

Votre entrée est une liste non vide d'entiers L , prise dans n'importe quel format raisonnable. Votre sortie est le plus petit entier N tel que L peut être aléatoire bloc triée de sorte que le nombre de blocs et la longueur de chaque bloc sont au plus N .

Le nombre d'octets le plus bas dans chaque langue gagne. Les règles de code-golf standard s'appliquent.

Cas de test

[5] -> 1
[1,2] -> 2
[0,2,1,-1] -> 3
[-1,0,2,1] -> 2
[9,3,8,2,7] -> 4
[9,2,8,3,7] -> 3
[5,9,3,7,2,4,8] -> 7
[-1,-2,1,2,-1,-2,7] -> 4
[6,1,0,3,2,4,-2,-1] -> 4
[12,5,6,-6,-1,0,2,3] -> 3
[1,0,1,0,1,0,1,0,1,0] -> 6
[1,2,1,3,1,2,3,2,4,3] -> 5
[7,7,7,7,8,9,7,7,7,7] -> 4

Brachylog , 23 22 20 19 octets

Merci à Zgarb, H.PWiz et Fatalize d'avoir économisé une certaine quantité d'octets.

~cᶠ{oᵐoc≤₁&≡ᵃlᵐ⌉}ˢ⌋

Essayez-le en ligne!

Je suis sûr qu'il y a plus à jouer au golf ici ...

Explication

~cᶠ      Find all lists that concatenate into the input, i.e. all partitions
         of the input.
{        Discard all partitions for which this predicate fails, and replace
         the rest with the output of this predicate.
  oᵐ       Sort each sublist of the partition.
  o        Sort the entire list.
  c≤₁      And require concatenation of the result to be sorted.
  &        Then:
  ≡ᵃ       Append the partition to itself.
  lᵐ       Map "length" over this list, i.e. we get the length of each block, as
           well as the length of the partition itself.
  ⌉        Take the maximum.
}ˢ
⌋        Take the minimum of all those maxima.

Gelée , 17 octets

Ṣ€ṢF
ŒṖÇÐṂ+Z$€L€Ṃ

Essayez-le en ligne!

Version alternative, 15 octets, défi postdates

Dans la dernière version, Ɗcombine trois maillons en une chaîne monadique. Cela permet le golf suivant.

ŒṖṢ€ṢFƊÐṂ+ZLƊ€Ṃ

Essayez-le en ligne!

Comment ça fonctionne

Ṣ€ṢF          Helper link. Argument: P (partitioned array)

Ṣ€            Sort each chunk.
  Ṣ           Sort the sorted chunks.
   F          Flatten.


ŒṖÇÐṂ+Z$€L€Ṃ  Main link. Argument: A (array)

ŒṖ            Generate all partitions of A.
  ÇÐṂ         Keep those for which the helper link returns the minimal array, i.e.,
              those that return sorted(A).
     +Z$€     Add each partition to its transpose.
              Due to how Jelly vectorizes, the length of the sum is the maximum of
              the length of the operands, and the length of the transpose is the
              length of the array's largest column.
         L€   Take the length of each sum.
           Ṃ  Take the minimum.

Stax , 28 26 25 24 23 octets ^CP437

é%(>ù│ê²☻û◙T╠►╜◘íaæAtI╥

Exécutez et déboguez en ligne!

Crédits à @recursive pour avoir économisé 3 octets.

Stax est un peu bavard ici. Il faut deux octets pour trier un tableau par défaut, deux octets pour obtenir le maximum / minimum d'un tableau et deux octets pour aplatir un tableau. Quoi qu'il en soit, je poste toujours la solution et j'espère qu'il pourra y avoir des suggestions utiles sur la façon de l'améliorer .

Explication

Utilise la version décompressée pour expliquer.

%cFxs|!F{{omo:f:^!C_Mch\%|m
%cFxs|!F                        Do for all partitions, grouped by number of sub-arrays
                                    Grouping by number of sub-arrays in this problem does not help but it's the default                    
        {{om{o                  Sort inside block then sort blocks lexicographically
              :f:^              The result when flattened is sorted
                  !C            Skip the rest of the loop if the last line is false
                    _|<         Take the current partition, pad to the longest

                       h        Take the first element, whose length is now the maximum of all sub-arrays in the original partition
                        \       Zip with the current partition, the shorter one is repeated
                         %      Number of elements
                                Which is the maximum of all sub-array sizes and the number of sub-arrays in the current partition  
                          |m    Take the minimum among all choices of partitions

Brachylog , 17 octets

~c₎{oᵐoc≤₁&lᵐ⌉≤}ᵈ

Essayez-le en ligne!

Explication

C'est une auto-réponse; J'ai conçu ce défi en pensant à Brachylog et j'ai trouvé~c₎{…}ᵈ une construction intéressante.

Le intégré cconcatène une liste de listes. Si on lui donne un indice N, il faut que le nombre de listes soit N. Le symbole ₎modifie un intégré pour prendre une paire en entrée et utiliser son élément droit comme indice. Prend donc c₎une paire [L,N], nécessite que le nombre de listes dans Lsoit N, et retourne la concaténation de L. Lorsqu'il est exécuté en sens inverse, ~c₎prend une liste Let renvoie une paire [P,N], où se Ptrouve une partition de Len Nblocs. Ils sont énumérés par ordre croissant de N.

Le métaprédicat ᵈtransforme un prédicat ordinaire en un prédicat qui vérifie une relation entre les deux éléments d'une paire. Plus explicitement, {…}ᵈprend une paire [A,B], vérifie que c'est le cas A{…}Bet sort B. Je l'utilise pour vérifier qu'il Ppeut être trié par blocs et ne contient que des listes de longueur au maximum N.

~c₎{oᵐoc≤₁&lᵐ⌉≤}ᵈ  Input is a list, say L = [9,2,8,3,7].
~c₎                Guess the pair [P,N]: [[[9],[2],[8,3,7]],3]
   {           }ᵈ  Verify this predicate on P and N and return N:
    oᵐ              Sort each list in P: [[9],[2],[3,7,8]]
      o             Sort lexicographically: [[2],[3,7,8],[9]]
       c            Concatenate: [2,3,7,8,9]
        ≤₁          This list is nondecreasing: true.
          &lᵐ       Length of each list in P: [1,1,3]
             ⌉      Maximum: 3
              ≤     This is at most N: true.

Notez que Ppeut contenir des listes vides. Cela garantit l'exactitude également dans les cas où la longueur maximale d'un bloc est supérieure au nombre de blocs.

Python 2 , 186 146 octets

lambda l:min(max(map(len,z+[z]))for z in p(l)if sum(s(z),[])==s(l))
p=lambda l:[q+[s(l[i:])]for i in range(len(l))for q in p(l[:i])]or[l]
s=sorted

Essayez-le en ligne!

La deuxième fonction est extraite de cette astuce par feersum .

Rubis , 158 octets

f=->l,i=[],s=l.size,m=s{k=*l;i.sum==s&&i.map{|z|k.shift(z).sort}.sort.flatten==l.sort&&[m,[i.size,*i].max].min||i.sum<s&&(1..s).map{|z|f[l,i+[z],s,m]}.min||m}

Essayez-le en ligne!

Pyth ,  24 23  20 octets

hSmeSlMs]Bd.msSSMb./

Suite de tests.

Comment ça fonctionne

hSmeSlMs]Bd.msSSMb./ – Full program. Hereby, Q represents the input.
                  ./ – All possible partitions of Q.
           .m        – Take the partitions which yield a minimal (i.e. sorted) list over:
             sSSMb   – Sorting function. Uses the variable b.
               SMb   – Sort each list in each partition b.
              S      – Sort the partition b.
             s       – And flatten (by 1 level).
  meSlMs]Bd          – Map. Uses a function whose variable is d.
        ]Bd          – Pair d with its wrapping in a singleton list. Returns [d, [d]].
       s             – Flatten (by 1 level). Returns [*d, d], where "*" is splatting.
     lM              – Take the length of each element.
   eS                – Retrieve the maximal length.
hS                   – Return the minimum element of the list of maximal lengths.

APL (Dyalog Classic) , 71 67 octets

{⌊/(⌈/≢,≢¨)¨T/⍨{S[⍋S]≡∊⍵[⍋↑⍵]}¨T←{⍵[⍋⍵]}¨¨⊂∘S¨(-≢S)↑¨2⊥⍣¯1¨⍳2*≢S←⍵}

⎕IO doit être 0

Essayez-le en ligne!

Comment?

• ⌊/- Trouvez le minimum de ...
• (⌈/≢,≢¨)- ... le maximum de la longueur et du nombre d'éléments ...
• ¨- ... de chaque élément de ...
• T/⍨- ... les éléments qui ...
• {S[⍋S]≡∊⍵[⍋↑⍵]}¨- ... sont triés à plat, de ...
• T←{⍵[⍋⍵]}¨¨- ... les éléments triés des éléments de ...
• ⊂∘S¨(-≢S)↑¨2⊥⍣¯1¨⍳2*≢S←⍵- ... les partitions de l'argument (avec quelques ordures)