Shuffle-Sortierung blockieren

Die Block-Shuffle-Sortierung ist eine (eher künstliche) Methode zum Sortieren einer Liste. Es funktioniert wie folgt, anhand eines Beispiels.

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

Die Aufteilung in zusammenhängende Blöcke kann beliebig gewählt werden. Nicht alle Auswahlmöglichkeiten von Blöcken führen jedoch am Ende zu einer sortierten Liste:

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

Wenn alle Blöcke die Länge 1 haben oder wenn es nur einen Block gibt, wird das Ergebnis natürlich sortiert. Dies sind aber eher Extremfälle. In dieser Herausforderung besteht Ihre Aufgabe darin, ein Gleichgewicht zwischen der Anzahl der Blöcke und der maximalen Länge eines Blocks zu finden.

Die Aufgabe

Ihre Eingabe ist eine nicht leere Liste von Ganzzahlen L , die in einem beliebigen vernünftigen Format eingegeben werden. Ihre Ausgabe soll die kleinste Ganzzahl N sein, so dass L blockweise sortiert werden kann, so dass die Anzahl der Blöcke und die Länge jedes Blocks höchstens N beträgt .

Die niedrigste Byteanzahl in jeder Sprache gewinnt. Es gelten die Standardregeln für Code-Golf .

Testfälle

[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 Bytes

Vielen Dank an Zgarb, H.PWiz und Fatalize für die Einsparung einiger Bytes.

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

Probieren Sie es online!

Ich bin mir sicher, dass es hier mehr zum Golfen gibt ...

Erläuterung

~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.

Gelee , 17 Bytes

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

Probieren Sie es online!

Alternative Version, 15 Byte, Herausforderung nach Datum

ƊKombiniert in der neuesten Version drei Glieder zu einer monadischen Kette. Dies ermöglicht folgendes Golfen.

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

Probieren Sie es online!

Wie es funktioniert

Ṣ€Ṣ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 Byte ^CP437

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

Online ausführen und debuggen!

Dank an @recursive für das Speichern von 3 Bytes.

Stax ist hier ein bisschen wortreich. Es sind zwei Bytes erforderlich, um ein Array standardmäßig zu sortieren, zwei Bytes, um das Maximum / Minimum eines Arrays abzurufen, und zwei Bytes, um ein Array zu reduzieren. Wie auch immer, ich poste die Lösung immer noch und hoffe, es gibt hilfreiche Vorschläge, wie man sie verbessern kann .

Erläuterung

Verwendet die entpackte Version, um zu erklären.

%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 Bytes

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

Probieren Sie es online!

Erläuterung

Dies ist eine Selbstantwort; Ich habe diese Herausforderung mit Blick auf Brachylog entworfen und ~c₎{…}ᵈein interessantes Konstrukt gefunden.

Das eingebaute cverkettet eine Liste von Listen. Wenn ein Index angegeben wird N, muss die Anzahl der Listen angegeben werden N. Das Symbol ₎ändert ein eingebautes Element, um ein Paar als Eingabe zu verwenden und sein rechtes Element als Index zu verwenden. Somit c₎nimmt ein Paar [L,N]erfordert, dass die Anzahl der Listen List N, und gibt die Verkettung L. Bei umgekehrter Ausführung ~c₎wird eine Liste erstellt Lund ein Paar zurückgegeben [P,N], bei dem Pes sich um eine Aufteilung Lin NBlöcke handelt. Sie werden in aufsteigender Reihenfolge von aufgelistet N.

Das Metapredikat ᵈwandelt ein gewöhnliches Prädikat in ein Prädikat um, das eine Beziehung zwischen den beiden Elementen eines Paares überprüft. Nimmt genauer {…}ᵈgesagt ein Paar [A,B], prüft das A{…}Bund gibt es aus B. Ich benutze es, um zu überprüfen, ob Pes blockweise sortiert werden kann und nur Listen mit maximaler Länge enthält 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.

Beachten Sie, dass Pmöglicherweise leere Listen enthalten sind. Dies stellt die Korrektheit auch in den Fällen sicher, in denen die maximale Länge eines Blocks größer als die Anzahl der Blöcke ist.

Python 2 , 186 146 Bytes

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

Probieren Sie es online!

Die zweite Funktion wird von feersum von diesem Tipp übernommen .

Ruby , 158 Bytes

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}

Probieren Sie es online!

Pyth ,  24 23  20 Bytes

hSmeSlMs]Bd.msSSMb./

Testsuite.

Wie es funktioniert

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 Bytes

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

⎕IO muss sein 0

Probieren Sie es online!

Wie?

• ⌊/- Finden Sie das Minimum von ...
• (⌈/≢,≢¨)- ... das Maximum der Länge und Anzahl der Elemente ...
• ¨- ... von jedem Element von ...
• T/⍨- ... die Elemente, die ...
• {S[⍋S]≡∊⍵[⍋↑⍵]}¨- ... werden abgeflacht sortiert, von ...
• T←{⍵[⍋⍵]}¨¨- ... die sortierten Elemente der Elemente von ...
• ⊂∘S¨(-≢S)↑¨2⊥⍣¯1¨⍳2*≢S←⍵- ... die Partitionen des Arguments (zusammen mit etwas Müll)