Come posso assicurarmi che quando rimescolo il mio puzzle finisca comunque con una permutazione uniforme?

Question

Mi interessa fare un'implementazione del 14-15 puzzle:

Sto creando un array con i valori 0 - 15 in ordine crescente:

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

Ora, quello che voglio fare è mescolarli per creare una nuova istanza del puzzle. Tuttavia, so che se creo una scacchiera con una "permutazione dispari" piuttosto che irrisolvibile.

Wikipedia dice che ho bisogno di creare il puzzle con una permutazione pari. Credo che questo significhi che devo semplicemente assicurarmi di fare un numero pari di swap?

Come modificherei Fisher-Yates in modo da assicurarmi di ottenere una permutazione uniforme alla fine? Se faccio uno swap per ogni elemento dell'array, sarebbero 16 swaps che credo sarebbe una permutazione pari. Tuttavia, devo preoccuparmi di scambiare se stesso? C'è un altro modo per assicurarmi di avere un puzzle valido?

Answer 1

Non vorrei davvero provare a modificare l'algoritmo stesso, è comunque discutibile per questa applicazione. Da quello che vedo ci sono due opzioni:

1. Ri-shuffle solo fino a ottenere una permutazione pari. Questo probabilmente eliminerebbe mediamente una permutazione media (beh, forse un po 'di più), ma il lavoro extra è molto probabilmente trascurabile.
2. Mescola il tabellone usando le mosse del gioco stesso. Cioè, fai solo poche centinaia di mosse casuali. Dal momento che non stai prendendo tutti i pezzi e riassemblandoli non puoi generare uno stato impossibile da risolvere.

Answer 2

Fisher-Yates dipende dalla possibilità di scambiare qualsiasi elemento con qualsiasi altro elemento. Poiché questo viola la fisica del puzzle, non penso che tu possa usarlo qui.

La soluzione ingenua è di fare quello che si potrebbe fare manualmente, in modo casuale selezionare una delle tessere adiacenti a quello vuoto e di swap con esso. Non so quanti swap avresti bisogno di fare per ottenere un buon shuffle.

Answer 3

Dovresti essere in grado di utilizzare Fischer-Yates.

• Generare una permutazione casuale usando Fischer-Yates.
• Verificare se è pari.
• Se non è pari, scambia i primi due elementi della permutazione.

Considerare una permutazione pari P = x1 x2 .... xn.

Fischer genera P con probabilità 1/n !.

Genera x2 x1 ... xn con probabilità 1/n !.

Quindi la probabilità che il processo precedente generi la permutazione P è 2/n! = 1/(n!/2)

n!/2 è il numero di permutazioni pari.

quindi il processo sopra genera permutazioni con stessa probabilità.

Per verificare se una permutazione è pari: contare la parità del numero di inversions nella permutazione.

Answer 4

Ecco cosa ho trovato già risposto qui:.

"Questo problema si riduce sostanzialmente verso il basso per fare un algoritmo casuale standard con un piccolo tocco di

L'osservazione fondamentale è che per la 15-puzzle per essere risolvibile la parità della permutazione e la parità della piazza vuota deve essere lo stesso

Innanzitutto creare una permutazione casuale utilizzando un algoritmo standard per tale scopo, ad esempio l'algoritmo di riordino Knuth:.. casuale permutazioni

Il vantaggio di utilizzare riordino di Knuth (o Fisher-Yates shuffle) è che si tratta di scambiare i numeri, in modo da poter facilmente tenere traccia della parità della permutazione. Ogni scambio o mantiene la parità (se si scambia 1 & 3), o cambia la parità (se si scambia 1 & 2).

Posizionare casella della stessa parità, come la parità della permutazione, e si è fatto. Se la permutazione ha una parità dispari, metti lo spazio in bianco un quadrato dispari (1,3,5, ... scelto a caso). Se la permutazione ha parità pari, posiziona lo spazio vuoto su un quadrato pari. "

Inoltre," In pratica, all'incirca ogni 4 permutazioni generate consecutivamente consisteranno in due permutazioni pari e due dispari, quindi anche il costo di iterazione è trascurabile "

È inoltre possibile controllare questo sito fuori:. http://eusebeia.dyndns.org/epermute

Answer 5

RISPOSTA AGGIORNAMENTO:

Prima di introdurre questo algoritmo, ho bisogno di definire due termini:. inversione di polarità e

Inversion: Una coppia di oggetti che sono in ordine inverso, da dove dovrebbero essere. Per ulteriori informazioni sull'inversione, consultare Counting inversions in an array

La polarità di un puzzle è se il numero totale di inversioni tra tutte le tessere è pari o dispari. Un puzzle con 10 inversioni ha persino polarità; un puzzle con 7 inversioni ha una strana polarità.

Considerare 3x3 puzzle come questo:

| 6 | 3 | 2 |

| .. | 4 | 7 |

| 5 | 1 | 0 |

Conteggio di tutte le inversioni qui, otteniamo: (i) 6 è invertito con 0, 1, 2, 3, 4 e 5. (ii) 3 è invertito con 0, 1 e 2. (iii) 2 è invertito con 0 e 1. (iv) 4 è invertito con 0 e 1. (v) 7 è invertito con 0, 1 e 5. (vi) 5 è invertito con 0 e 1. (vii) 1 è invertito con 0. in totale ci sono 19 inversioni.

Se la larghezza del puzzle è un numero pari, spostare una tessera su o giù invertirà la polarità, quindi è importante che il puzzle abbia polarità pari quando la tessera vuota è nell'ultima riga.Per questo aggiungeremo la distanza della tessera vuota dalla riga inferiore alla nostra inversione totale.

Ora sappiamo che un puzzle è risolvibile è ha anche polarità (o permutazioni). Quindi, se la nostra polarità è anche allora il nostro problema è risolto ma per strana polarità dobbiamo fare questo:

Se la tessera vuota non è nella prima riga, allora scambia le prime due tessere adiacenti nella prima fila. Questo cambierà la polarità di 1 e avremo un puzzle risolvibile con polarità uniforme.

Ma se il riquadro vuoto è nella prima riga, scambiare le tessere adiacenti nell'ultima riga. Ciò renderebbe il puzzle risolvibile. Quindi alla fine finisci sempre con un puzzle risolvibile.

Spero di soddisfare i requisiti di risposta dello stackoverflow per questa domanda. Ogni dubbio è apprezzato. Grazie.