Un shuffle riffle est un type de shuffle où le pont est divisé en deux partitions et les partitions sont ensuite épissées ensemble pour créer un nouveau pont mélangé.

Les cartes sont épissées ensemble de telle sorte que les cartes conservent leur ordre relatif dans la partition à laquelle elles appartiennent . Par exemple, si la carte A est avant la carte B dans le jeu et que les cartes A et B sont dans la même partition, la carte A doit être avant la carte B dans le résultat final, même si le nombre de cartes entre elles a augmenté. Si A et B sont dans des partitions différentes, ils peuvent être dans n'importe quel ordre, quel que soit leur ordre de départ, dans le résultat final.

Chaque mélange de fusils peut ensuite être considéré comme une permutation du jeu de cartes d'origine. Par exemple la permutation

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

est un remaniement rapide. Si vous divisez le jeu comme ça

1, 2 | 3

nous voyons que chaque carte dans 1,3,2a le même ordre relatif à toutes les autres cartes dans sa partition. 2est toujours après 1.

D'un autre côté, la permutation suivante n'est pas un shuffle riffle.

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

Nous pouvons le voir parce que pour les deux partitions (non triviales)

1, 2 | 3
1 | 2, 3 

il y a une paire de cartes qui ne maintiennent pas leur ordre relatif. Dans la première partition 1et 2changez leur ordre, tandis que dans la deuxième partition 2et 3changez leur ordre.

Cependant, nous voyons que cela 3, 2, 1peut être fait en composant deux shuffles de fusil,

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

En fait, un fait assez simple à prouver est que toute permutation peut être effectuée en combinant un certain nombre de permutations de shuffle de riffle.

Tâche

Votre tâche consiste à créer un programme ou une fonction qui prend une permutation (de taille N ) en entrée et génère le plus petit nombre de permutations de réarrangement de riffle (de taille N ) pouvant être combinées pour former la permutation d'entrée. Vous n'avez pas besoin de sortir les réorganisations de fusils elles-mêmes, juste combien il y en a.

Il s'agit de code-golf donc les réponses seront notées en octets avec moins d'octets mieux.

Vous pouvez sortir 1 ou 0 pour une permutation d'identité.

Cas de test

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 octets

Vérifie tous les riffles possibles jusqu'à la longueur de la liste (nombre maximum requis), il est donc très lent pour une entrée plus importante. Pourrait probablement aussi être joué un peu au golf.

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

Essayez-le en ligne!

Nettoyer , 206 ... 185 octets

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]

Essayez-le en ligne!

Génère tous les résultats possibles des ntemps de mélange et vérifie si la liste est membre.
Bien que ce soit une façon horriblement inefficace de résoudre le problème, ce code est particulièrement lent en raison de son utilisation des listes de compréhension au lieu de la composition, ce qui limite fortement toute réduction élémentaire du graphique, et se traduit par une vitrine spectaculaire du garbage collector de Clean.

Non golfé:

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

Essayez-le en ligne!