javascript - 查找排列反转的数量

Question

我在看 this因为我正在尝试制作一个十五分谜解算器。我真的不明白它在说什么。我将如何检查给定的一组数字(从 0-15，存储在数组中，0 为空白)是否有效，因为“如果列表的排列符号是 +1，则该位置是可能的”。如果相关的话，我正在使用 javascript。

Answer 1

请考虑以下情况:如果您解决了一个 15 字谜题，并且将一对胶合板物理移除并交换并替换了 14 和 15 block ，然后打乱它...你能把它恢复到有效状态吗？

答案是否定的。在 15 拼图中，您可以执行的所有移动都保留了一个不变量，而排列符号可能指的是该不变量。

根据 http://en.wikipedia.org/wiki/Fifteen_puzzle :

The invariant is the parity of the permutation of all 16 squares (15 pieces plus empty square) plus the parity of the taxicab distance moved by the empty square.

This is an invariant because each move changes both the parity of the permutation and the parity of the taxicab distance. In particular if the empty square is not moved the permutation of the remaining pieces must be even.

要计算此奇偶校验，请查看 http://en.wikipedia.org/wiki/Parity_of_a_permutation (您也可以查看 Levi-Civita Symbol，但它有点神秘)，在 python 中实现它，然后计算空方 block 从其起始位置移动的曼哈顿距离，并取这两个值之和的奇偶校验。

类似于:

#!/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

以下是一些示例/测试用例:

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))

结果:

| 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

如果你的算法并不真正关心这个位置是否可能(你这样做只是为了说“无效输入!位置不可能!”你可以忽略这部分，无论如何运行它几百迭代，如果未解决则返回“不可能!”。