Blokuj sortowanie losowe

Blok losowe sortowania jest (raczej sztuczny) sposób sortowania listy. Działa w następujący sposób, ilustrowany przykładem.

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

Podział na ciągłe bloki można wybrać dowolnie. Jednak nie wszystkie wybory bloków dają posortowaną listę na końcu:

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

Jeśli wszystkie bloki mają długość 1 lub jeśli jest tylko jeden blok, wynik zostanie oczywiście posortowany. Ale są to raczej skrajne przypadki. W tym wyzwaniu Twoim zadaniem jest znalezienie równowagi między liczbą bloków a maksymalną długością bloku.

Zadanie

Twój wkład jest niepustą listą liczb całkowitych L , wykonaną w dowolnym rozsądnym formacie. Jego wynik jest najmniejszą liczbę całkowitą N , tak że L może być bloku losowego posortowane tak, że liczba bloków i długość poszczególnych bloków w większości N .

Najniższa liczba bajtów w każdym języku wygrywa. Obowiązują standardowe zasady gry w golfa .

Przypadki testowe

[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 bajtów

Dzięki Zgarb, H.PWiz i Fatalize za zaoszczędzenie pewnej ilości bajtów.

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

Wypróbuj online!

Jestem pewien, że jest tu coś do golfa ...

Wyjaśnienie

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

Galaretka , 17 bajtów

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

Wypróbuj online!

Alternatywna wersja, 15 bajtów, wyzwanie postdate

W najnowszej wersji Ɗłączy trzy linki w monadyczny łańcuch. Umożliwia to następujące golfa.

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

Wypróbuj online!

Jak to działa

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

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

Uruchom i debuguj online!

Kredyty dla @recursive za zapisanie 3 bajtów.

Stax jest tutaj trochę gadatliwy. Domyślnie sortowanie tablicy zajmuje dwa bajty, dwa bajty, aby uzyskać maksimum / minimum tablicy, i dwa bajty, aby spłaszczyć tablicę. W każdym razie wciąż publikuję rozwiązanie i mam nadzieję, że mogą być pomocne sugestie, jak je poprawić .

Wyjaśnienie

Używa rozpakowanej wersji do wyjaśnienia.

%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 bajtów

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

Wypróbuj online!

Wyjaśnienie

To jest odpowiedź na pytanie; Zaprojektowałem to wyzwanie z myślą o Brachylog i znalazłem ~c₎{…}ᵈinteresującą konstrukcję.

Wbudowana ckonkatenuje listę list. Jeśli ma indeks dolny N, wymagana jest liczba list N. Symbol ₎modyfikuje wbudowane, aby pobierać parę jako dane wejściowe i używać prawego elementu jako indeksu dolnego. Zatem c₎trwa parę [L,N]wymaga, aby liczba wykazów w Lto N, i zwraca konkatenacji L. Podczas działania w odwrotnej kolejności ~c₎pobiera listę Li zwraca parę [P,N], gdzie Pjest podział Lna Nbloki. Są one wyliczane w porządku rosnącym N.

Metapredykat ᵈprzekształca zwykły predykat w taki, który sprawdza relację między dwoma elementami pary. Mówiąc ściślej, {…}ᵈbierze parę [A,B], sprawdza, które A{…}Btrzyma i generuje B. Używam go do sprawdzenia, czy Pmożna go posortować według bloków i czy zawiera on tylko listy długości 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.

Uwaga: Pmoże zawierać puste listy. Zapewnia to poprawność również w tych przypadkach, w których maksymalna długość bloku jest większa niż liczba bloków.

Python 2 , 186 146 bajtów

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

Wypróbuj online!

Druga funkcja pochodzi z tej wskazówki przez feersum .

Rubin , 158 bajtów

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}

Wypróbuj online!

Pyth ,  24 23  20 bajtów

hSmeSlMs]Bd.msSSMb./

Zestaw testowy.

Jak to działa

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 bajtów

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

⎕IO musi być 0

Wypróbuj online!

W jaki sposób?

• ⌊/ - Znajdź minimum ...
• (⌈/≢,≢¨) - ... maksymalna długość i liczba elementów ...
• ¨ - ... każdego elementu ...
• T/⍨ - ... elementy, które ...
• {S[⍋S]≡∊⍵[⍋↑⍵]}¨ - ... są sortowane po spłaszczeniu, z ...
• T←{⍵[⍋⍵]}¨¨ - ... posortowane elementy elementów ...
• ⊂∘S¨(-≢S)↑¨2⊥⍣¯1¨⍳2*≢S←⍵- ... partycje argumentu (wraz z niektórymi śmieciami)