Riffling Cards в Mathematica

Question

Мой друг задал мне этот вопрос; хотелось поделиться этим здесь.

Учитывая колоду карт, мы разделяем ее на 2 группы и "чередуем их"; давайте назовем эту операцию «split-join». И повторите ту же операцию с полученной колодой.

Например, , {1, 2, 3, 4} становится {1, 2} & {3, 4} (сплит) и мы получаем {1, 3, 2, 4} (объединение)

Кроме того, если у нас есть нечетное количество карт, то есть {1, 2, 3} , мы можем разделить его следующим образом: {1, 2} & {3 } (первая половина больше), ведущая к {1, 3, 2} (т. е. n делится на Ceil[n/2] & n-Ceil[n/2])

Она задала мне вопрос:

СКОЛЬКО таких сплит-объединений необходимо, чтобы вернуть исходную колоду?

И это заставило меня задуматься:

Если в колоде n карт, какое количество сплит-объединений необходимо, если:

• n чётно?
• n нечетно?
• n является степенью '2'? [Я обнаружил, что тогда нам нужно log (n) (base 2) количество сплит-объединений ...]
• (Не стесняйтесь исследовать различные сценарии, подобные этому.)

Существует ли простой шаблон / формула / концепция, коррелирующая n и необходимое количество разделенных объединений?

Я считаю, что это хорошая вещь для изучения в Mathematica, особенно, поскольку она предоставляет метод Riffle[].

Answer 1

Цитировать MathWorld :

Число сторонних перемешиваний, необходимых для возврата колоды с n = 2, 4, ... в первоначальный порядок, составляет 1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6. , 11, ... (A002326 Слоана), который является просто мультипликативным порядком 2 (mod n-1). Например, колода из 52 карт возвращается в исходное состояние после восьми перестановок, так как 2 ** 8 = 1 (мод 51) (Golomb 1961). Наименьшее количество карт 2n, которым для возврата в исходное состояние колоды требуется 1, 2, 3, ... out-shuffles, составляет 1, 2, 4, 3, 16, 5, 64, 9, 37, 6, .. . (Слоана А114894).

Случай, когда n нечетен, не рассматривается.

Обратите внимание, что статья также включает в себя записную книжку Mathematica с функциями для изучения перестановок.

Answer 2

Если у нас нечетное количество карточек n==2m-1, и если мы разделяем карточки так, что во время каждого перемешивания первая группа содержит m карточек, вторая группа m-1 карточек и группы объединяются так, чтоникакие две карты одной группы не оказываются рядом друг с другом, тогда необходимое количество перемешиваний равно MultiplicativeOrder[2, n].

Чтобы показать это, отметим, что после одного тасования карта, которая находилась в позиции k, переместилась в позицию 2k для 0<=k<m и в 2k-2m+1 для m<=k<2m-1, где kтаков, что 0<=k<2m-1.Записано по модулю n==2m-1 это означает, что новая позиция Mod[2k, n] для всех 0<=k<n.Поэтому, чтобы каждая карта вернулась в исходное положение, нам нужно N тасов, где N таков, что Mod[2^N k, n]==Mod[k, n] для всех 0<=k<n, из которых следует, что N является кратным MultiplicativeOrder[2, n].

Обратите внимание, что из-за симметрии результат был бы точно таким же, если бы мы разделили колоду наоборот, т.е. первая группа всегда содержит m-1 карт, а вторая группа m карт.Я не знаю, что произойдет, если вы чередуетесь, то есть для нечетных перемешиваний первая группа содержит m карт, а для четных перемешиваний m-1 карт.

Answer 3

Есть старая работа мага / математика Перси Диаконниса о восстановлении ордена с помощью совершенных перемешиваний. Ян Стюарт писал об этой работе в одной из своих колонок «Научно-американский математический отдых» 1998 года - см., Например: http://www.whydomath.org/Reading_Room_Material/ian_stewart/shuffle/shuffle.html

Answer 4

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

 countrifflecards[deck_] := Module[{n = Length@deck, ct, rifdeck},
      ct = 0;
      rifdeck = 
        Riffle @@ 
          Partition[ # , Ceiling[ n/2], Ceiling[ n/2], {1, 1}, {} ] &;
      NestWhile[(++ct; rifdeck[#]) &, deck, #2 != deck &,2 ]; ct]

Это обрабатывает четные и нечетные случаи:

 countrifflecards[RandomSample[ Range[#], #]] & /@ Range[2, 52, 2]

{1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8}

 countrifflecards[RandomSample[ Range[#], #]] & /@ Range[3, 53, 2]

{2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10, 12, 36, 12, 20, 14, 12, 23, 21, 8, 52}

Вы можете легко показать, если вы добавите карту в нечетный случай, дополнительная карта останется внизуи не изменяйте последовательность, следовательно, результатом нечетного случая является просто n+1 четный результат ..

 ListPlot[{#, countrifflecards[RandomSample[ Range[#], #]]} & /@ 
      Range[2, 1000]]