¿Cómo puedo asegurarme de que cuando baraje mi acertijo termine con una permutación uniforme?

Question

me interesa hacer una aplicación de la 14-15 puzzle:

estoy creando una matriz con los valores de 0 - 15 en orden creciente:

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

Ahora, lo que quiero hacer es mezclarlos para crear una nueva instancia del rompecabezas. Sin embargo, sé que si creo una placa con una "permutación impar" no es posible resolverla.

Wikipedia dice que necesito crear el rompecabezas con una permutación uniforme. Creo que esto significa que simplemente tengo que asegurarme de hacer un número par de swaps.

¿Cómo puedo modificar Fisher-Yates para asegurarme de que termine con una permutación uniforme al final? Si hago un intercambio por cada elemento de la matriz, serían 16 intercambios que creo que serían una permutación uniforme. Sin embargo, ¿debo preocuparme por el intercambio consigo mismo? ¿Hay alguna otra forma de asegurarme de tener un acertijo válido?

Answer 1

Realmente no intentaría alterar el algoritmo en sí, probablemente sea discutible para esta aplicación. Por lo que veo, hay dos opciones:

1. Simplemente vuelve a mezclar hasta obtener una permutación uniforme. Esto probablemente arrojaría media permutación en promedio (bueno, tal vez un poco más), pero el trabajo extra es muy poco significativo.
2. Mezcla el tablero usando los movimientos del juego. Es decir, solo haz algunos cientos de movimientos aleatorios. Ya que no está quitando todas las piezas y volviendo a ensamblarlas, no puede generar un estado que sea imposible de resolver.

Answer 2

Fisher-Yates depende de la capacidad de intercambiar cualquier elemento con cualquier otro elemento. Como esto viola la física del rompecabezas, no creo que puedas usarlo aquí.

La solución ingenua es hacer lo que harías manualmente, selecciona aleatoriamente una de las casillas adyacentes a la vacía e intercambia con ella. No sé cuántos intercambios tendrías que hacer para obtener una buena mezcla.

Answer 3

Debería poder usar Fischer-Yates.

• Genera una permutación aleatoria utilizando Fischer-Yates.
• Compruebe si es par.
• Si no es par, intercambie los dos primeros elementos de la permutación.

Considere una permutación uniforme P = x1 x2 .... xn.

Fischer yates genera P con probabilidad 1/n !.

Genera x2 x1 ... xn con probabilidad 1/n !.

Por lo tanto, la probabilidad de que el proceso anterior genere la permutación P es 2/n! = 1/(n!/2)

n!/2 es el número de permutaciones par.

Por lo tanto, el proceso anterior genera incluso permutaciones con la misma probabilidad.

Para comprobar si una permutación es par: cuente la paridad del número de inversions en la permutación.

Answer 4

Esto es lo que ya ha encontrado aquí la respuesta:.

"Este problema básicamente se reduce a hacer un algoritmo aleatorio de serie con un pequeño giro

La observación clave es que para el 15-rompecabezas para ser solucionable la paridad de la permutación y la paridad del cuadrado en blanco debe ser el mismo

en primer lugar crear una permutación aleatoria utilizando un algoritmo estándar para tal fin, por ejemplo el algoritmo aleatorio Knuth:.. permutaciones aleatorias

La ventaja de utilizar la mezcla aleatoria de Knuth (o mezcla aleatoria de Fisher-Yates) es que implica el intercambio de números, por lo que puede realizar un seguimiento de la paridad de la permutación. Cada intercambio mantiene la paridad (si cambia 1 & 3) o cambia la paridad (si cambia 1 & 2).

Coloque el cuadrado en blanco en la misma paridad que la paridad de la permutación, y listo. Si la permutación tiene una paridad impar, coloque el espacio en blanco en un cuadrado impar (1,3,5, ... elegido al azar). Si la permutación tiene paridad par, entonces coloque el espacio en blanco en un cuadrado par. "

Además," En la práctica, aproximadamente cada 4 permutaciones generadas consecutivamente consistirán en dos permutaciones pares y dos permutaciones impares, por lo que incluso el costo por iteración es insignificante "

también puede comprobar este sitio hacia fuera:. http://eusebeia.dyndns.org/epermute

Answer 5

RESPUESTA ACTUALIZADO:

Antes de presentar este algoritmo, tengo que definir dos términos:. inversión de polaridad y

Inversión: un par de objetos que están en el orden inverso al que deberían estar. Para obtener más información sobre la inversión, consulte Counting inversions in an array

La polaridad de un rompecabezas es si el número total de inversiones entre todas las fichas es par o impar. Un rompecabezas con 10 inversiones tiene incluso polaridad; un rompecabezas con 7 inversiones tiene una polaridad impar.

Considere el rompecabezas 3x3 como este:

| 6 | 3 | 2 |

| .. | 4 | 7 |

| 5 | 1 | 0 |

Contando todas las inversiones aquí, obtenemos: (i) 6 se invierte con 0, 1, 2, 3, 4 y 5. (ii) 3 se invierte con 0, 1 y 2. (iii) 2 es invertido con 0 y 1. (iv) 4 se invierte con 0 y 1. (v) 7 se invierte con 0, 1 y 5. (vi) 5 se invierte con 0 y 1. (vii) 1 se invierte con 0. En total tenemos inversiones.

Si el ancho del rompecabezas es un número par, mover una ficha hacia arriba o hacia abajo invierte la polaridad, por lo que es importante que el rompecabezas tenga polaridad pareja cuando la ficha vacía esté en la última fila.Para esto agregaremos la distancia del mosaico vacío desde la fila inferior a nuestras inversiones totales.

Ahora sabemos que un rompecabezas se puede resolver si tiene polaridad par (o permutaciones). Entonces, si nuestra polaridad es incluso entonces nuestro problema está resuelto, pero para la polaridad impar tenemos que hacer esto:

Si el mosaico vacío no está en la primera fila, entonces intercambie los dos primeros mosaicos adyacentes en la primera fila. Esto cambiará la polaridad en 1 y tendremos un rompecabezas solucionable con polaridad pareja.

Pero si el mosaico está vacío en la primera fila, cambie las fichas adyacentes en la última fila. Esto haría el rompecabezas solucionable. Así que al final siempre terminas con un rompecabezas solucionable.

Espero cumplir los requisitos de respuesta de stackoverflow para esta pregunta. Cualquier duda es apreciada. Gracias.