找到排列倒置的数量

Question

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

Answer 1

请考虑以下事项:如果您采用了解决的15-puzzle,并且将一对plyers物理移除并交换并替换了14和15块,并将其加扰......您是否可以将其恢复到有效状态？

答案是不.你可以在15个谜题中做的所有动作都保留了一个不变量,而置换符号可能指的是那个不变量.

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

不变量是所有16个方格(15个加空方格)的排列的奇偶性加上空方格移动的出租车距离的奇偶校验.

这是一个不变量,因为每次移动都会改变排列的奇偶性和出租车距离的奇偶性.特别是如果没有移动空方块,则剩余部分的排列必须是均匀的.

要计算这个奇偶校验,请查看http://en.wikipedia.org/wiki/Parity_of_a_permutation(你也可以查看Levi-Civita符号,但它有点神秘),在python中实现它,然后计算曼哈顿距离为空square已从其起始位置移开,并取两个值的总和.

就像是:

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

如果你的算法并不真正关心位置是否可能(你只是这样说"无效输入!位置不可能!"你可以忽略这部分,无论如何都要运行它几百次迭代,并且返回"不可能!"如果未解决.