Рифловое перемешивание - это тип перемешивания, в котором колода разделена на два раздела, а затем разделены, чтобы создать новую перемешанную колоду.

Карты объединяются таким образом, что карты сохраняют свой относительный порядок в пределах раздела, членом которого они являются . Например, если карта A находится перед картой B в колоде, а карты A и B находятся в одном и том же разделе, карта A должна быть перед картой B в конечном результате, даже если количество карт между ними увеличилось. Если A и B находятся в разных разделах, они могут быть в любом порядке, независимо от их начального порядка, в конечном результате.

Каждый случай перемешивания может быть рассмотрен как перестановка оригинальной колоды карт. Например перестановка

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

это риффл шаффл. Если вы разделите колоду так

1, 2 | 3

мы видим, что каждая карта 1,3,2имеет одинаковый относительный порядок по отношению к любой другой карте в своем разделе. 2все еще после 1.

С другой стороны, следующая перестановка не является случайным перемешиванием.

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

Мы можем видеть это, потому что для всех двух (нетривиальных) разбиений

1, 2 | 3
1 | 2, 3 

есть пара карт, которые не поддерживают свои относительные порядки. В первом разделе 1и 2измените их порядок, а во втором разделе 2и 3измените их порядок.

Тем не менее, мы видим, что это 3, 2, 1может быть сделано путем составления двух перемешиваний,

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

На самом деле довольно простой факт, который нужно доказать, состоит в том, что любая перестановка может быть сделана путем объединения некоторого числа перестановок с риффл-тасовкой.

задача

Ваша задача состоит в том, чтобы создать программу или функцию, которая принимает перестановку (размером N ) в качестве входных данных и выводит наименьшее количество перестановок в произвольном порядке (размера N ), которые можно объединить для формирования входной перестановки. Вам не нужно выводить сами риффл-тасовки, сколько их есть.

Это код-гольф, поэтому ответы будут оцениваться в байтах, причем меньшее количество байтов будет лучше.

Вы можете вывести 1 или 0 для перестановки идентификаторов.

Тестовые случаи

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 байт

Проверяет все возможные риффы до длины списка (требуется максимальное количество), поэтому он очень медленный для большего ввода. Возможно также, может быть, в гольф совсем немного.

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

Попробуйте онлайн!

Чисто , 206 ... 185 байт

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]

Попробуйте онлайн!

Генерирует все возможные результаты перемешивания nи проверяет, является ли список участником.
Хотя это ужасно неэффективный способ решения проблемы, этот код особенно медленный из-за использования в нем компоновок списков вместо композиции, что сильно ограничивает уменьшение элементарного графа и приводит к впечатляющей демонстрации сборщика мусора 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

Попробуйте онлайн!