Losowanie riffle jest rodzajem losowania, w którym talia jest podzielona na dwie partycje, a następnie partycje są łączone z powrotem, aby utworzyć nową tasowaną talię.

Karty są łączone ze sobą w taki sposób, że karty zachowują swój względny porządek w obrębie partycji, której są członkami . Na przykład, jeśli karta A znajduje się przed kartą B w talii, a karty A i B znajdują się w tej samej partycji, karta A musi znajdować się przed kartą B w wyniku końcowym, nawet jeśli liczba kart między nimi wzrosła. Jeśli A i B znajdują się w różnych partycjach, mogą być w dowolnej kolejności, niezależnie od kolejności początkowej, w wyniku końcowym.

Każde losowanie karabinów można następnie traktować jako permutację oryginalnej talii kart. Na przykład permutacja

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

jest losowym tasowaniem. Jeśli tak podzielisz talię

1, 2 | 3

widzimy, że każda karta w 1,3,2tej samej kolejności względem każdej innej karty na partycji. 2jest nadal po 1.

Z drugiej strony poniższa permutacja nie jest przetasowaniem riffla.

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

Widzimy to, ponieważ dla wszystkich dwóch (nietrywialnych) partycji

1, 2 | 3
1 | 2, 3 

istnieje para kart, które nie zachowują względnej kolejności. W pierwszej partycji 1i 2zmień ich kolejność, podczas gdy w drugiej partycji 2i 3zmień ich kolejność.

Widzimy jednak, że 3, 2, 1można to zrobić poprzez skomponowanie dwóch przetasowań karabinowych,

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

W rzeczywistości dość prostym faktem, który można udowodnić, jest to, że można dokonać dowolnej permutacji, łącząc pewną liczbę permutacji ruffle shuffle.

Zadanie

Twoim zadaniem jest stworzenie programu lub funkcji, która pobiera permutację (o rozmiarze N ) jako dane wejściowe i generuje najmniejszą liczbę permutacji losowych riffle (o rozmiarze N ), które można połączyć w celu utworzenia permutacji wejściowej. Nie trzeba samemu odtwarzać losowego tasowania riffów, ile ich jest.

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Możesz podać 1 lub 0 dla permutacji tożsamości.

Przypadki testowe

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 bajtów

Sprawdza wszystkie możliwe riffy aż do długości listy (wymagana maksymalna liczba), więc jest bardzo wolny dla większych danych wejściowych. Prawdopodobnie można by też trochę zagrać w golfa.

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

Wypróbuj online!

Czysty , 206 ... 185 bajtów

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]

Wypróbuj online!

Generuje każdy możliwy wynik nczasów przetasowania i sprawdza, czy lista jest członkiem.
Chociaż jest to strasznie nieefektywny sposób rozwiązania problemu, ten kod jest szczególnie wolny ze względu na użycie listowego rozumienia zamiast kompozycji, co mocno ogranicza dowolną redukcję grafów elementarnych i skutkuje spektakularną wizytówką śmieciarza Clean.

Nie golfowany:

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

Wypróbuj online!