Как я могу гарантировать, что, когда я тасую свою головоломку, я все равно получаю равномерную перестановку?

Question

Мне интересно сделать реализацию головоломки 14-15 :

Я создаю массив со значениями 0 - 15 в порядке возрастания:

S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

Теперь я хочу перетасовать их, чтобы создать новый экземпляр головоломки. Однако я знаю, что если я создаю доску с «нечетной перестановкой», то это неразрешимо.

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

Как бы я изменил Фишера-Йейтса, чтобы в конце я получил ровную перестановку? Если я сделаю перестановку для каждого элемента в массиве, это будет 16 перестановок, которые, я считаю, будут четной перестановкой. Тем не менее, я должен быть обеспокоен обменом с самим собой? Есть ли другой способ убедиться, что у меня есть правильная головоломка?

Answer 1

Вы должны быть в состоянии использовать Фишера-Йейтса.

• Генерация случайной перестановки с использованием Фишера-Йейтса.
• Проверьте, четное ли это.
• Если оно не четное, поменяйте местами первые два элемента перестановки.

Рассмотрим четную перестановку P = x1 x2 .... xn.

Фишер Йейтс генерирует P с вероятностью 1 / n!.

Генерирует x2 x1 ... xn с вероятностью 1 / n!.

Таким образом, вероятность того, что вышеуказанный процесс генерирует перестановку P, равна 2 / n! = 1 / (n! / 2)

n! / 2 - число четных перестановок.

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

Чтобы проверить, четна ли перестановка: посчитайте четность числа инверсий в перестановке.

Answer 2

Вот что я нашел здесь уже ответил:

"Эта проблема в основном сводится к выполнению стандартного алгоритма тасования с небольшим поворотом.

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

Сначала создайте случайную перестановку, используя для этого стандартный алгоритм. Например, алгоритм Кнута тасования: случайные перестановки

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

Поместите пустой квадрат в ту же четность, что и четность перестановки, и все готово. Если перестановка имеет нечетную четность, тогда поместите пробел в нечетный квадрат (1,3,5, ... выбранный случайным образом). Если перестановка имеет четную четность, поместите пробел на четный квадрат. "

Кроме того, «На практике примерно каждые 4 последовательно сгенерированных перестановки будут состоять из двух четных и двух нечетных перестановок, поэтому даже стоимость каждой итерации незначительна».

Вы также можете проверить этот сайт: http://eusebeia.dyndns.org/epermute

Answer 3

ОБНОВЛЕННЫЙ ОТВЕТ:

Прежде чем я представлю этот алгоритм, мне нужно определить два термина: инверсия и полярность.

Инверсия: пара объектов, которые находятся в обратном порядке от того, где они должны быть. Для получения дополнительной информации об инверсии см. Подсчет инверсий в массиве

Полярность головоломки состоит в том, является ли общее число инверсий среди всех плиток четным или нечетным. Головоломка с 10 инверсиями имеет четную полярность; головоломка с 7 инверсиями имеет странную полярность.

Считайте головоломку 3х3 такой:

| 6 | 3 | 2 |

| .. | 4 | 7 |

| 5 | 1 | 0 |

Подсчитав здесь все инверсии, мы получим: (i) 6 инвертировано с 0, 1, 2, 3, 4 и 5. (ii) 3 инвертировано с 0, 1 и 2. (iii) 2 инвертировано с 0 и 1. (iv) 4 инвертируется с 0 и 1. (v) 7 инвертируется с 0, 1 и 5. (vi) 5 инвертируется с 0 и 1. (vii) 1 инвертируется с 0. В Всего у нас 19 инверсий.

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

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

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

Но если пустая плитка находится в первом ряду, то поменяйте местами соседние плитки в последнем ряду. Это сделало бы головоломку разрешимой. Так что в конце вы всегда решаете головоломку.

Надеюсь, я удовлетворяю отвечающим требованиям stackoverflow для этого вопроса. Любые сомнения приветствуются. Спасибо.

Answer 4

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

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

Answer 5

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

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