Идеальное перемешивание

Идеальное перемешивание

Исследуя математику, лежащую в основе тасования фаро, отвечая на вопрос: сколько точных перетасовок необходимо, чтобы вернуть колоду карт в ее первоначальный порядок?

Это было 2 года назад, когда я наткнулся на колоду игральных карт ремесленников. Гладкий, с неоново-красным акцентом, я купил его, не особо задумываясь. Я никогда особо не умел обращаться с картами, раскладывать карты веером или тасовать фаро было для меня трудным делом. Но эта новая колода карт вселила в меня достаточно ложной уверенности, чтобы попытаться овладеть ею еще раз.

Прогресс был постепенным, но меня все больше привлекала таинственность простой колоды карт. Это было, когда я испытал момент r / ShowerThoughts.

Сколько раз мне нужно перетасовать карты, чтобы вернуть их в исходный порядок?

Как вы, наверное, догадались, я был не на том уровне, на котором я могу легко перетасовать 52 карты 8 раз, чтобы понять, что потребовалось такое количество перетасовок, чтобы вернуть их в исходный порядок. В конце концов, я написал простой скрипт для перетасовки.

Я построил результаты на линейном графике (Рис.1), и что сразу привлекло мое внимание, так это выявившаяся закономерность.

Я не мог объяснить, почему потребовалось всего 14 перетасовок для колоды из 384 карт, тогда как для колоды из 54 карт потребовалось 52 перетасовки. Еще один интересный паттерн - это «вершины» графика, идеально образующие прямую линию. Это начинало становиться немного сложнее ...

Я выбрал r / math в надежде найти ответ. Он получил несколько длинных объяснений (за которые я благодарен) со ссылкой на функцию модуля и степень двойки. Освоив базовую математику в средней школе, я изо всех сил пытался понять интуицию, лежащую в основе отвечает и медленно просто оставил все как есть.

Перенесемся в сегодняшний день, когда я работал в последний день Пришествия кода, когда наткнулся на Проблема дискретного логарифма (DLP). Функция Тотента Эйлера Φ (n) возникла как важная концепция, когда я пытался решить проблему DLP.

Общая функция Φ (n), также называемая общей функцией Эйлера, определяется как количество положительных целых чисел ‹= n, которые взаимно просты с (т. Е. Не содержат каких-либо общих множителей) n .

При поиске функции totient я обнаружил пояснительную страницу с линейным графиком функции totient для диапазона положительных целых чисел (рис. 2). Охваченный сильным чувством дежавю, я узнал знакомые закономерности.

Функция totient чем-то напоминает соотношение между количеством перетасовок, необходимых для восстановления колоды из n карт. Сразу же в моей голове начали формироваться гипотезы, в которых я был убежден, что каким-то образом секреты идеального перемешивания имеют какое-то отношение к дискретному логарифму и функции Totient.

The Faro Shuffle

Прежде чем я начну вдаваться в математику, давайте посмотрим, что значит «совершенная» / фаро перетасовка.

Чтобы перетасовать фаро, вы сначала разделяете колоду на 2 равные части, а затем переплетаете их по одной карте за раз, комбинируя их.

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

Перемешать

При перемешивании исходная верхняя и нижняя карты останутся в исходном положении.

В случайном порядке

При перемешивании исходная верхняя карта перемещается на вторую, а исходная нижняя карта перемещается на вторую снизу.

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

Чтобы укрепить эту интуицию, совершенно необходимо выразить перемешивание фаро математическим способом.

Что происходит после перетасовки?

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

Перемешать

Мы начинаем с маркировки позиций каждой карточки с помощью системы нулевой индексации. Первая карта в колоде будет иметь позицию 0, тогда как последняя карта карты будет занимать позицию N-1, где N представляет собой общее количество карт в колоде .

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

Позиции 0, 1,..., n-2, n-1 относятся к первой половине, где его первая карта имеет значение позиции 0, а последняя карта имеет значение позиции n-1. Точно так же с позициями n, n+1,..., 2n-1, 2n-1, принадлежащими второй половине, его первая карта будет иметь значение позиции n, тогда как его последняя карта будет иметь значение позиции 2n-1.

Это измененное обозначение позволяет нам разделить колоду на две отдельные половины, что дает нам более естественное выражение при моделировании тасования.

Так как верхняя и нижняя карты колоды останутся неизменными, только внутренняя часть колоды изменится после одного тасования.

Мы можем визуализировать конечные позиции каждой карты после единственного перетасовки как таковой:

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

В случайном порядке

Следуя той же системе нумерации с нулевым индексом, мы можем выразить результат перетасовки колоды карт, как мы сделали для перетасовки карт.

После перетасовки все карты меняют свое положение, в отличие от перетасовки.

Результат перемешивания можно выразить так:

Первоначальная верхняя карта становится второй картой сверху, а исходная нижняя карта поднимается, чтобы занять место второй карты снизу.

Можем ли мы сжать это в элегантное уравнение?

В перетасовке есть определенная закономерность, ведь интуиция подсказывает нам, что это просто кладет одну карту из одной половины на карту из другой половины.

Переплетение обоих типов перемешивания, несомненно, можно свести в элегантное уравнение.

Перемешать

Для простоты давайте воспользуемся колодой из 6 карт, чтобы визуализировать перетасовку.

После однократного перемешивания исходная карточка в позиции 1 перемещается в позицию 2, а исходная карточка в позиции 2 перемещен в позицию 4. Если вы сразу заметили этот паттерн, было бы неправильно сказать, что, возможно, после перетасовки положение изменилось с функцией 2 × исходное положение. Однако, изучая другие карты, вы понимаете, что это не подходит для всех карт, особенно из второй половины.

Причина, по которой функция 2 × исходная позиция хорошо работает для первой половины, заключается в том, что результат напрямую равен количеству карт, которые будут предшествовать одной карте в первой половине после аута. перемешать.

Фактически, мы можем думать об этом так же и для второй половины карт, только это не совсем очевидно. Переплетение при перемешивании одинаково для обеих половин карт, и, следовательно, если функции 2 × исходное положение достаточно для определения окончательного положения карт в первой половине, возможно, мы прямо на пороге общего уравнения.

Такое же переплетение происходит во второй половине карточек, но функция 2 × исходное положение дает нам конечное положение, которое превышает максимальное положение. Что, если мы просто «завернем» его?

Применяя оператор по модулю, мы «оборачиваем» результат функции 2 × исходное положение и можем достичь правильной позиции для карт во второй половине.

Добавление дополнительного оператора по модулю к функции 2 × исходное положение дает нам общее (и довольно элегантное) уравнение, которое мы искали.

В случайном порядке

Мы можем применить тот же эксперимент с 6 картами, чтобы визуализировать перемешивание.

После единственного перемешивания мы видим, что верхняя и нижняя карты поменялись местами. Исходная карточка в позиции 0 перемещена в позицию 1, а исходная карточка в позиции 1 перемещена в позицию 3.

В этот момент вы поняли, что уравнение, которое мы только что обнаружили, очевидно, не подходит для перемешивания. Но что, если мы просто добавим к нему знак +1?

Вы снова в восторге, поэтому начинаете тестировать на второй половине карточек…

Разочаровавшись, вы поняли, что 2j mod (2n-1) + 1 не будет обобщать на вторую половину карты. Но будучи очень решительным, вы обнаружили, что 2j-1 mod (2n-1) работает во второй половине. Использование условной функции для представления одной операции в случайном порядке становится беспорядочным.

Единственная разница между переплетением при перемешивании и перемешиванием при перемешивании состоит в том, что половина карт «поднимается» над другой. При перетасовке первая половина карт размещается над второй и наоборот.

Интуитивно понятно, что не должно быть большой разницы между общим уравнением перетасовки и перетасовки.

Мы знаем, что при перемешивании уравнение 2j mod (2n-1) даст нам количество карт, которые будут предшествовать отдельной карте после перемешивания. Он также удобно равен конечному положению карты. Это отчасти связано с хорошими свойствами системы нумерации с нулевым индексом.

Думая в том же духе, нам нужно уравнение с этими свойствами для перемешивания. Система индексирования с нуля не сработала, но как насчет системы индексации с нуля?

Использование системы индексации на основе одного:

Простое изменение системы индексирования пока не помогает. Нам нужно пересмотреть, как нам нужно будет изменить нашу логику «упаковки» / операнд по модулю.

Поскольку мы используем систему индексации на основе единицы, наше общее уравнение не должно давать нулевое значение. Выполняя простой тест, если бы мы назначили операнду по модулю 6, исходная карточка в позиции 4 будет иметь окончательное значение 0. если мы используем уравнение 2j mod (2n), где 2n - позиция последней карты.

Следовательно, чтобы мы могли поддерживать индексирование на основе единицы, наш операнд по модулю должен иметь вид 2n + 1.

Собрав все вместе, мы получили наше общее (и столь же элегантное) уравнение для перемешивания.

Множественное перемешивание

Теперь, когда у нас есть уравнения для представления как входящих, так и исходящих перетасовок, давайте выясним, где будет располагаться конкретная карта после n перетасовок.

По сути, это простая проблема рекурсии, которую мы решаем.

Написание простого скрипта Python для запуска этой рекурсии было бы простой задачей (просто увеличьте размер стека для большого n), однако часто понимание правильных математических концепций вместо рекурсий с использованием грубой силы дает нам беспрецедентный прирост производительности.

Модульная арифметика

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

Результат предыдущей операции будет введен в следующую операцию, и этот цикл будет повторяться до тех пор, пока колода не завершит n перетасовок. Время выполнения, конечно, не будет долгим, но давайте попробуем упростить его, чтобы немного ускорить его.

Давайте рассмотрим всего 2 перетасовки:

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

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

Мы только что победили рекурсии!

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

Вернуться к исходному вопросу…

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

Сколько фаро-перетасовок нужно, чтобы перетасовать колоду карт в исходный порядок?

Мы изучили способы математического выражения двух различных типов тасования фаро и рассмотрели уравнения, которые помогли нам выяснить, в каком положении окажется карта после n тасовок. До сих пор мы рассматривали проблему с уровня отдельной карты, следующим шагом будет обобщение ее для всей колоды.

Колода карт возвращается в исходный порядок, когда каждая карта возвращается в исходное положение.

Переводя эту интуицию в математические термины, мы получаем следующее:

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

Мы видим, что теперь мы можем обрабатывать операцию перемешивания независимо от исходного положения карты. Что еще лучше, так это то, что операция перемешивания моделируется после задачи дискретного логарифма.

Наконец-то мы его нашли!

Сосредоточение внимания исключительно на операции перемешивания даст немного более сжатое уравнение для решения:

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

Когда k = 1, мы полностью удовлетворяем уравнению без утомительной работы.

В конце концов, даже алгоритмы искусственного интеллекта иногда думают, что это лучший способ выиграть игру. Хотя с технической точки зрения это вполне приемлемый и логичный ответ, он дает нулевую ценность для проблемы.

Это означает, что, возможно, нам потребуется установить важное ограничение: k должно быть не менее 1.

Решение DLP

Мы можем упростить уравнение и обобщить его до общей проблемы дискретного логарифмирования. Вкратце, модульный операнд 2n-1 & 2n + 1 близко соответствует системе индексации, которую мы выбрали для моделирования как исходящего, так и входящего соответственно. Однако при попытке упростить проблему до общего DLP форма 2n-1 & 2n + 1 не имеет математического значения. Мы можем просто представить их положительным целым числом X.

Есть много способов решить DLP, будь то грубая сила или алгоритм Baby Step Giant Step (BSGS). Вы также можете ускорить процесс, реализовав алгоритм Поляга – Хеллмана.

Я не буду вдаваться в подробности DLP или различных методов его решения, поскольку он заслуживает отдельной статьи. Но для полноты картины я включил простую реализацию BSGS, написанную на python, которую я использовал для решения уравнения.

Вернуться к графику

Этот линейный график был создан путем ручного моделирования операции перемешивания. После сжатия фаро до «простого» DLP мы теперь можем проверить, соответствует ли наш новый подход и работает ли он хорошо.

Я наложил результаты решения DLP (оранжевая линия) поверх результата ручного моделирования (синий оттенок).

Мы видим, что он идеально совмещен и служит визуальным и количественным доказательством того, что мы успешно смоделировали проблему как задачу дискретного логарифма.

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

Когда мы сравниваем 2 линейных графика, мы видим, что на самом деле есть небольшая и интересная разница.

Красной линией отмечены точки, в которых необходимо такое же количество перетасовок, чтобы вернуть колоду карт в исходное положение. Что интересно, так это то, что линейный график количества необходимых перетасовок кажется «отстает» от графика исходящих. Присмотревшись, мы видим, что количество перетасовок, необходимых для N карт, такое же, как количество перетасовок, необходимых для N-2 карты, фактически делая перемешивание «на один шаг» позади исходящего.

Ключевая интуиция возникает из важной детали, которую мы исследовали ранее. Перетасовка не влияет на верхнюю и нижнюю карту колоды, она только меняет положение карт между ними, в отличие от всех карт, меняющих свои позиции при перемешивании.

Но как тасуются карты посередине между верхней и нижней картами во время перетасовки?

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

Игнорируя верхнюю и нижнюю карты, положение которых не изменилось, мы видим, что средняя часть перетасовывается до странности знакомым образом.

Выделив среднюю часть колоды, мы поняли, что все ее позиции изменятся после перетасовки. Это похоже на перемешивание, и, когда мы внимательно посмотрим, как меняются его позиции, он идентичен перемешиванию.

Каждая перетасовка - это, по сути, перетасовка верхних и нижних карт.

Думаю, было бы неуместным сказать, что перетасовка в основном состоит из перетасовки, просто добавляются две дополнительные карты на концах, которые не будут перемешиваться в процессе.

Но подождите ... а что насчет пиков?

Поразительной деталью представленных мною графиков является наличие «пиков», когда мы тасуем определенное количество карт. «Пики» и «впадины» являются причиной того, почему требуется 52 перетасовки колоды из 54 карт, чтобы восстановить ее порядок, в отличие от всего 14 перетасовок для колоды из 384 карт . Это, мягко говоря, не интуитивно понятно, но, возможно, изучение функции Тотента Эйлера Φ (n) может дать нам отправную точку.

Когда мы строим график функции totient, мы видим тот же образец «пиков». Еще один интересный момент, который следует отметить, - это то, что «пики» образуют линейную линию.

Функция totient дает нам количество натуральных чисел до заданного целого числа n, которые взаимно просты с n. Пики соответствуют простым целым числам как Φ (n) = n-1. Таким образом, прямая следует по форме линии y = x -1.

Возможно, простые целые числа как-то связаны с нашей проблемой перетасовки.

Мы знаем, что можем сконцентрировать проблему перетасовки в DLP, на самом деле, очень специфическом виде DLP.

Так получилось, что теорема Эйлера имеет относительно похожую форму и дает нам лучшее представление о том, как функция totient связана с нашей проблемой перетасовки.

Давайте посмотрим, почему для колоды из 54 карт необходимо 52 перетасовки карт.

Сразу становится ясно, что когда мы вводим числа, наш модуль становится простым целым числом. Следуя теореме Эйлера, показатель степени будет результатом тотальной функции по модулю. Поскольку 53 простое число, найдутся 53 - 1 положительных целых чисел, взаимно простых с ним, в результате чего показатель степени 52 года.

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

В качестве общего заключительного утверждения, «пики», таким образом, находятся в точках, где количество карт в колоде дает простое по модулю, будь то разложенное или перетасованное.

Теперь мы взломали внутреннюю работу идеального тасования.

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