Uma reprodução aleatória de rifles é um tipo de reprodução aleatória em que o baralho é dividido em duas partições e as partições são então unidas novamente para criar um novo baralho baralhado.

Os cartões são unidos de maneira que os cartões mantenham sua ordem relativa na partição da qual são membros . Por exemplo, se o cartão A estiver antes do cartão B no baralho e os cartões A e B estiverem na mesma partição, o cartão A deverá estar antes do cartão B no resultado final, mesmo que o número de cartões entre eles tenha aumentado. Se A e B estiverem em partições diferentes, eles poderão estar em qualquer ordem, independentemente da ordem inicial, no resultado final.

Cada baralhamento de rifles pode ser visto como uma permutação do baralho de cartas original. Por exemplo, a permutação

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

é uma reprodução aleatória. Se você dividir o baralho assim

1, 2 | 3

vemos que cada cartão 1,3,2tem a mesma ordem relativa a todos os outros cartões em sua partição. 2ainda está depois 1.

Por outro lado, a permutação a seguir não é uma reprodução aleatória.

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

Podemos ver isso porque para todas as duas partições (não triviais)

1, 2 | 3
1 | 2, 3 

há um par de cartas que não mantêm suas ordens relativas. Na primeira partição 1e 2altere sua ordem, enquanto na segunda partição 2e 3altere sua ordem.

No entanto, vemos que isso 3, 2, 1pode ser feito compondo dois shuffles rifles,

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

De fato, um fato bastante simples a ser provado é que qualquer permutação pode ser feita pela combinação de um certo número de permutações de ruffle shuffle.

Tarefa

Sua tarefa é criar um programa ou função que use uma permutação (de tamanho N ) como entrada e produza o menor número de permutações de ruffle shuffle (de tamanho N ) que podem ser combinadas para formar a permutação de entrada. Você não precisa produzir os ruffles aleatoriamente apenas quantos existem.

Isso é código-golfe, então as respostas serão pontuadas em bytes, com menos bytes sendo melhores.

Você pode gerar 1 ou 0 para uma permutação de identidade.

Casos de teste

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

Python 3 , 255 bytes

Verifica todos os riffles possíveis até o comprimento da lista (número máximo necessário), por isso é muito lento para entradas maiores. Provavelmente também poderia ser jogado bastante.

lambda x:f(range(1,len(x)+1),x)
f=lambda x,y,i=0:x==y and i or i<len(x)and min(f(q,y,i+1)for a in range(1,len(x))for q in g(x[:a],x[a:]))or i
g=lambda x,y:(x or y)and[[v]+q for v in x[:1]for q in g(x[1:],y)]+[[v]+q for v in y[:1]for q in g(x,y[1:])]or[[]]

Experimente online!

Limpo , 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]

Experimente online!

Gera todos os resultados possíveis de ntempos de embaralhamento e verifica se a lista é um membro.
Embora essa seja uma maneira terrivelmente ineficiente de resolver o problema, esse código é particularmente lento devido ao uso de compreensão de lista em vez de composição, o que limita fortemente qualquer redução elementar de gráfico e resulta em uma mostra espetacular do coletor de lixo do Clean.

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

Experimente online!