How many shuffles

Question

A riffle shuffle is a type of shuffle where the deck is split into two partitions and the partitions are then spliced back together to create a new shuffled deck.

The cards are spliced together in such a way that cards maintain their relative order within the partition they are a member of. For example, if card A is before card B in the deck and cards A and B are in the same partition, card A must be before card B in the final result, even if the number of cards between them has increased. If A and B are in different partitions, they can be in any order, regardless of their starting order, in the final result.

Each riffle shuffle can then be viewed as a permutation of the original deck of cards. For example the permutation

1,2,3 -> 1,3,2

is a riffle shuffle. If you split the deck like so

1, 2 | 3

we see that every card in 1,3,2 has the same relative order to every other card in it's partition. 2 is still after 1.

On the other hand the following permutation is not a riffle shuffle.

1,2,3 -> 3,2,1

We can see this because for all the two (non-trivial) partitions

1, 2 | 3
1 | 2, 3 

there is a pair of cards that do not maintain their relative orderings. In the first partition 1 and 2 change their ordering, while in the second partition 2 and 3 change their ordering.

However we do see that 3, 2, 1 can be made by composing two riffle shuffles,

1, 3, 2 + 2, 3, 1 = 3, 2, 1

In fact a pretty simple fact to be proven is that any permutation can be made my combining some number of riffle shuffle permutations.

Task

Your task is to make a program or function that takes a permutation (of size N) as input and outputs the smallest number of riffle shuffle permutations (of size N) that can be combined to form the input permutation. You do not need to output the riffle shuffles themselves just how many there are.

This is code-golf so answers will be scored in bytes with fewer bytes being better.

You may output either 1 or 0 for an identity permutation.

Test Cases

1,3,2 -> 1
3,2,1 -> 2
3,1,2,4 -> 1
2,3,4,1 -> 1
4,3,2,1 -> 2

• mbomb007: So, will we be seeing RiffleSort algorithms soon?
• Wheat Wizard: @HalvardHummel That's correct. I'll have to find the issue with my reference implementation.

Answer 1

Clean, (削除) 206 (削除ここまで) ... 185 bytes

import StdEnv
f=flatten
$a b#[c:d]=b
|a>[]#[u:v]=a
=[a++b,b++a:f[[[u,c:e],[c,u:e]]\\e<- $v d]]=[b]
@l#i=length l
=hd[n\\n<-[0..],e<-iter n(f o map(uncurry$o splitAt(i/2)))[[1..i]]|l==e]

Try it online!

Generates every possible outcome of shuffling n times, and checks if the list is a member.
While this is a horribly inefficient way to solve the problem, this code is particularly slow due to its use of list comprehensions instead of composition, which heavily limits any elementary graph reduction, and results in a spectacular showcase of Clean's garbage collector.

Ungolfed:

import StdEnv
shuffle [] l
 = [l]
shuffle [a: b] [c: d]
 = [[a: b]++[c: d], [c: d]++[a: b]: flatten [
 [[a, c: e], [c, a: e]]
 \\ e <- shuffle b d
 ]]
numReq l
 = until cond ((+)1) 0
where
 cond n 
 = let
 mapper
 = map (uncurry shuffle o splitAt (length l/2))
 options
 = iter n (removeDup o flatten o mapper) [[1..length l]]
 in isMember l options

Try it online!