Как я могу удостовериться, чтобы, когда я переставляю свою загадку, я все еще закончил с ровной перестановкой?
Мне интересно, делая реализацию загадки 14-15: 
Я создаю массив со значениями 0 - 15 в увеличивающемся порядке:
S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
Теперь, то, что я хочу сделать, переставляют их для создания нового экземпляра загадки. Однако я знаю, что, если я создаю плату с "нечетной подстановкой", чем он, неразрешимо.
Википедия говорит, что я должен создать загадку с ровной перестановкой. Я полагаю, что это означает, что я просто должен сделать, гарантируют, чтобы я сделал четное число подкачек?
Как я изменил бы Фишера-Йетса, таким образом, я удостоверяюсь, чтобы я закончил с ровной перестановкой в конце? Если бы я делаю подкачку для каждого элемента в массиве, который был бы 16 подкачками, которым я верю, была бы ровная перестановка. Однако я должен быть обеспокоен свопингом с собой? Там какой-либо другой путь состоит в том, чтобы гарантировать, чтобы у меня была допустимая загадка?
3 ответа
Я бы не стал пытаться изменять сам алгоритм, в любом случае это, вероятно, спорно для этого приложения. Из того, что я вижу, есть два варианта:
- Просто перемешайте, пока не получите ровную перестановку. Это, вероятно, отбросит в среднем половину перестановки (ну, может быть, немного больше), но дополнительная работа, скорее всего, будет незначительной.
- Перетасуйте доску, используя ходы самой игры. То есть просто сделайте несколько сотен случайных ходов. Поскольку вы не извлекаете все части и не собираете их заново, вы не можете создать состояние, которое невозможно решить.
Фишер-Йейтс зависит от способности поменять местами любой элемент с любым другим элементом. Поскольку это нарушает физику головоломки, я не думаю, что вы можете использовать это здесь.
Наивное решение - сделать то, что вы делали бы вручную, случайным образом выбрать одну из плиток, смежных с пустой, и поменять местами с ней. Я не знаю, сколько свопов вам нужно сделать, чтобы хорошо перемешать.
Вы должны уметь использовать Fischer-Yates.
- Сгенерируйте случайную перестановку с помощью Фишера-Йейтса.
- Проверить четность.
- Если нет, поменяйте местами первые два элемента перестановки.
Рассмотрим четную перестановку P = x1 x2 .... xn.
Фишер Йейтс генерирует P с вероятностью 1 / n !.
Он генерирует x2 x1 ... xn с вероятностью 1 / n !.
Таким образом, вероятность того, что описанный выше процесс генерирует перестановку P, равна 2 / n! = 1 / (n! / 2)
n! / 2 - количество четных перестановок.
Таким образом, описанный выше процесс генерирует четные перестановки с одинаковой вероятностью.
Чтобы проверить, является ли перестановка четной: подсчитайте четность числа инверсий в перестановке.