Encontrar el número de inversiones de permutación

Question

Estaba buscando this porque estoy tratando de hacer un solucionador de quince rompecabezas. Realmente no entiendo de qué está hablando. ¿Cómo puedo verificar si un conjunto dado de números (de 0 a 15, almacenados en una matriz, 0 en blanco) es válido dado que "si el símbolo de permutación de la lista es +1, la posición es posible". Estoy trabajando en javascript, si es relevante.

Answer 1

Considere lo siguiente: Si tomó un 15 rompecabezas resuelto, y con un par de capas extraídas e intercambiadas físicamente y reemplazó los bloques 14 y 15, y lo revolvió ... ¿podría devolverlo a un estado válido?

la respuesta es no. Hay un invariante que se conserva mediante todos los movimientos que puede hacer en un rompecabezas de 15, y el símbolo de permutación probablemente se está refiriendo a ese invariante.

Según http://en.wikipedia.org/wiki/Fifteen_puzzle:

El invariante es la paridad de la permutación de los 16 cuadrados (15 piezas más cuadrado vacío), además de la paridad de la distancia de taxi movido por el cuadrado vacío.

Esto es un invariante porque cada movimiento cambia tanto la paridad de la permutación como la paridad de la distancia del taxi. En particular, si el cuadrado vacío no se mueve, la permutación de las piezas restantes debe ser par.

Para calcular esta paridad, echa un vistazo a http://en.wikipedia.org/wiki/Parity_of_a_permutation (también se podría retirar Levi-Civita Símbolo, pero es un poco arcano), lo apliquen en Python, a continuación, calcular la distancia Manhattan la plaza vacía ha movido de su partida posición, y tome la paridad de la suma de ambos valores.

Algo así como:

#!/usr/bin/python3 

from pprint import pprint 

state_starting = list(range(1,16)) + [None] 
START = state_starting 

def positionIsPossible(state): 
    """ 
     state is a list, the starting position is [1,2,3,...,15,None] 
    """ 
    numInversions = sum(
     state.index(START[j]) > state.index(START[i]) 
     for i in range(16) for j in range(i) # each pair (i,j) 
    ) #sum([True,True,False])==2 

    # Uncomment if you want to see what's going on here: 
    #pprint(list(
    # ((i,j), (START[i],START[j]), state.index(START[j]) > state.index(START[i])) 
    # for i in range(15) for j in range(i) 
    #)) 

    newEmptySquareYPos = state.index(None)//4 
    newEmptySquareXPos = state.index(None)%4 
    emptySquareMovedDistance = abs(3-newEmptySquareYPos)+abs(3-newEmptySquareXPos) 

    parity = (numInversions + emptySquareMovedDistance)%2 

    print('number of inversions:', numInversions) 
    print('distance empty square moved:', emptySquareMovedDistance) 
    print('parity:', parity) 

    return parity==0 

He aquí algunos ejemplos/casos de prueba:

def swap(state, i, j): 
    state = list(state) 
    state[i], state[j] = (state[j], state[i]) 
    return state 

def validate(state): 
    def formatState(state): 
     return '\n'.join('|'+' '.join([str(y if y else '').rjust(2) for y in x])+'|' for x in [state[0:4],state[4:8],state[8:12],state[12:16]]) 
    print(formatState(state)) 
    print(state, 'is', 'reachable' if positionIsPossible(state) else 'unreachable') 
    print() 

# reachable 
validate(state_starting) 
validate(swap(state_starting, 15,14)) 
validate(swap(state_starting, 15,11)) 

# unreachable 
validate(swap(state_starting, 14,13)) 

Resultados:

| 1 2 3 4|                                                              
| 5 6 7 8| 
| 9 10 11 12| 
|13 14 15 | 
number of inversions: 0 
distance empty square moved: 0 
parity: 0 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, None] is reachable 

| 1 2 3 4| 
| 5 6 7 8| 
| 9 10 11 12| 
|13 14 15| 
number of inversions: 1 
distance empty square moved: 1 
parity: 0 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, None, 15] is reachable 

| 1 2 3 4| 
| 5 6 7 8| 
| 9 10 11 | 
|13 14 15 12| 
number of inversions: 7 
distance empty square moved: 1 
parity: 0 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, None, 13, 14, 15, 12] is reachable 

| 1 2 3 4| 
| 5 6 7 8| 
| 9 10 11 12| 
|13 15 14 | 
number of inversions: 1 
distance empty square moved: 0 
parity: 1 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, None] is unreachable 

Si el algoritmo no le importa realmente acerca de si la posición es posible o no (solo está haciendo esto para decir "¡entrada no válida! ¡posición imposible!" podría ignorar esta parte, ejecútalo de todos modos por unos cientos de iteraciones, y devuelve "imposible" si no se resuelve.

Answer 2

Debido a los "ciclos" necesarios para mover las piezas en uno de estos rompecabezas, las permutas de piezas no se pueden realizar de forma aislada. Considere la pizarra:

debe cambiar (11) una (12) para resolverlo. Pero como puedes? Simplemente "ciclar" (11, 12, 15, -) en cualquier dirección nunca cambiará el orden. Por lo tanto, debemos involucrar más piezas, pero al hacerlo, no podemos preservar el orden de esas otras piezas. Todo lo que intentemos dará como resultado el cambio de otro par.Por ejemplo, podríamos corregir (11) y (12) con la participación de la (7) y (8), pero al hacerlo, cambie el (8) y (-):

Por lo tanto, el número de intercambios necesarios para resolver el rompecabezas debe ser uniforme, o nos queda un "hombre extraño" como en el tablero de arriba.

Por lo tanto, una vez más, si detecta en su solucionador una situación en la que un intercambio único resolverá el rompecabezas, sabrá que este tablero no puede ser resuelto.