Блок случайной сортировки

Блок перетасовка сортировка является (а искусственным) методом сортировки списка. Работает следующим образом, иллюстрируется примером.

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

Разбиение на смежные блоки может быть выбрано произвольно. Однако не все варианты блоков приведут к сортированному списку в конце:

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

Если все блоки имеют длину 1 или если имеется только один блок, то результат, конечно, будет отсортирован. Но это довольно крайние случаи. В этой задаче ваша задача - найти баланс между количеством блоков и максимальной длиной блока.

Задание

Ваш ввод представляет собой непустой список целых чисел L , взятых в любом приемлемом формате. Ваш вывод должен быть наименьшее целое число N такое , что L может быть блок воспроизведения в случайном порядке сортируются таким образом , что число блоков , а длина каждого блока находятся в большинстве N .

Наименьшее количество байтов в каждом языке выигрывает. Применяются стандартные правила игры в гольф .

Контрольные примеры

[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

Брахилог , 23 22 20 19 байт

Спасибо Zgarb, H.PWiz и Fatalize за сохранение некоторого количества байтов.

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

Попробуйте онлайн!

Я уверен, что здесь есть еще кое-что для гольфа ...

объяснение

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

Желе , 17 байт

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

Попробуйте онлайн!

Альтернативная версия, 15 байт, задание после даты

В последней версии Ɗобъединяет три звена в монадическую цепочку. Это позволяет следующий гольф.

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

Попробуйте онлайн!

Как это устроено

Ṣ€Ṣ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 байта ^CP437

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

Запускать и отлаживать онлайн!

Кредиты в @recursive для сохранения 3 байтов.

Стакс немного многословен здесь. Для сортировки массива по умолчанию требуется два байта, два байта для получения максимума / минимума массива и два байта для выравнивания массива. В любом случае, я все еще публикую решение и надеюсь, что будут полезные предложения о том, как его улучшить .

объяснение

Использует распакованную версию для объяснения.

%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

Брахилог , 17 байт

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

Попробуйте онлайн!

объяснение

Это самоответ; Я разработал эту задачу с учетом Brachylog и нашел ~c₎{…}ᵈинтересную конструкцию.

Встроенный cобъединяет список списков. Если ему дается нижний индекс N, для него требуется количество списков N. Символ ₎модифицирует встроенную функцию, чтобы взять пару в качестве входных данных и использовать ее правый элемент в качестве индекса. Таким образом , c₎занимает пару [L,N], необходимо, чтобы количество списков в Lэто N, и возвращает конкатенацию L. При обратном запуске ~c₎принимает список Lи возвращает пару [P,N], где Pесть разбиение Lна Nблоки. Они перечислены в порядке возрастания N.

Метапредикат ᵈпреобразует обычный предикат в один, который проверяет связь между двумя элементами пары. Более явно, {…}ᵈберет пару [A,B], проверяет, что A{…}Bдержит, и выводит B. Я использую его, чтобы убедиться, что он Pможет быть отсортирован по блокам и содержит только списки длины 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.

Обратите внимание, что Pмогут содержать пустые списки. Это обеспечивает корректность и в тех случаях, когда максимальная длина блока больше, чем количество блоков.

Python 2 , 186 146 байт

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

Попробуйте онлайн!

Вторая функция берется из этого наконечника по feersum .

Рубин , 158 байт

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}

Попробуйте онлайн!

Pyth ,  24 23  20 байт

hSmeSlMs]Bd.msSSMb./

Тестирование.

Как это устроено

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 байт

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

⎕IO должно быть 0

Попробуйте онлайн!

Как?

• ⌊/- Найти минимум ...
• (⌈/≢,≢¨)- ... максимальная длина и количество элементов ...
• ¨- ... каждого элемента ...
• T/⍨- ... элементы, которые ...
• {S[⍋S]≡∊⍵[⍋↑⍵]}¨- ... сортируются при выравнивании, из ...
• T←{⍵[⍋⍵]}¨¨- ... отсортированные элементы элементов ...
• ⊂∘S¨(-≢S)↑¨2⊥⍣¯1¨⍳2*≢S←⍵- ... разделы аргумента (вместе с мусором)