Sort by shuffling blocks

Question

Block shuffle sort

The block shuffle sort is a (rather artificial) method of sorting a list. It works as follows, illustrated by an example.

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

The partition into contiguous blocks can be chosen arbitrarily. However, not all choices of blocks will yield a sorted list at the end:

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

If all blocks have length 1, or if there is only one block, then the result will of course be sorted. But these are rather extreme cases. In this challenge, your task is to find a balance between the number of blocks and the maximum length of a block.

The task

Your input is a nonempty list of integers L, taken in any reasonable format. Your output shall be the smallest integer N such that L can be block shuffle sorted so that the number of blocks and the length of each block are at most N.

The lowest byte count in each language wins. Standard code-golf rules apply.

Test cases

[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

Answer 1

Brachylog, 23 22 20 19 bytes

Thanks to Zgarb, H.PWiz and Fatalize for saving some amount of bytes.

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

Try it online!

I'm sure there's more to golf here...

Explanation

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

Answer 2

Jelly, 17 bytes

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

Try it online!

Alternate version, 15 bytes, postdates challenge

In the latest version, Ɗ combines three links into a monadic chain. This allows the following golf.

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

Try it online!

How it works

Ṣ€Ṣ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.

Answer 3

Stax, 28 26 25 24 23 bytes^CP437

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

Run and debug online!

Credits to @recursive for saving 3 bytes.

Stax is a bit verbose here. It takes two bytes to sort an array by default, two bytes to get the maximum/minimum of an array and two bytes to flatten an array. Anyway I am still posting the solution and hope there can be helpful suggestions on how to improve it there is.

Explanation

Uses the unpacked version to explain.

%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

Answer 4

Brachylog, 17 bytes

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

Try it online!

Explanation

This is a self-answer; I designed this challenge with Brachylog in mind and found ~c₎{…}ᵈ an interesting construct.

The built-in c concatenates a list of lists. If it is given a subscript N, it requires the number of lists to be N. The symbol ₎ modifies a built-in to take a pair as input and use its right element as the subscript. Thus c₎ takes a pair [L,N], requires that the number of lists in L is N, and returns the concatenation of L. When run in reverse, ~c₎ takes a list L and returns a pair [P,N], where P is a partition of L into N blocks. They are enumerated in increasing order of N.

The metapredicate ᵈ transforms an ordinary predicate into one that checks a relation between the two elements of a pair. More explicitly, {…}ᵈ takes a pair [A,B], checks that A{…}B holds, and outputs B. I use it to verify that P can be block-sorted and only contains lists of length at most 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.

Note that P may contain empty lists. This ensures correctness also in those cases where the maximal length of a block is greater than the number of blocks.

Answer 5

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

Try it online!

The second function is taken from this tip by feersum.

Answer 6

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}

Try it online!

Answer 7

Pyth,  24 23  20 bytes

hSmeSlMs]Bd.msSSMb./

Test suite.

How it works

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.

Answer 8

APL (Dyalog Classic), 71 67 bytes

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

⎕IO must be 0

Try it online!

How?

• ⌊/ - Find the minimum of ...
• (⌈/≢,≢¨) - ... the maximum of the length and number of elements ...
• ¨ - ... of each element of ...
• T/⍨ - ... the elements that ...
• {S[⍋S]≡∊⍵[⍋↑⍵]}¨ - ... are sorted when flattened, of ...
• T←{⍵[⍋⍵]}¨¨ - ... the sorted elements of the elements of ...
• ⊂∘S¨(-≢S)↑¨2⊥⍣¯1¨⍳2*≢S←⍵ - ... the partitions of the argument (along with some junk)