Нахождение количества перестановочных инверсий

Question

Я смотрел на на , потому что я пытаюсь решить пятнадцать головоломок.Я не очень понимаю, о чем идет речь.Как бы я проверил, является ли данный набор чисел (от 0-15, сохраненный в массиве, 0 - пустым), допустим, учитывая, что «если символ перестановки списка равен +1, позиция возможна».Я работаю в JavaScript, если это уместно.

Answer 1

Подумайте о следующем: если вы взяли решенную 15-головоломку и физически удалили и обменяли пару плоскогубцев, заменили блоки 14 и 15 и взломали ее ... могли бы вы вернуть еедействительное состояние?

Ответ - нет.Существует инвариант, который сохраняется всеми ходами, которые вы можете выполнить в 15-головоломке, и символ перестановки, вероятно, относится к этому инварианту.

Согласно http://en.wikipedia.org/wiki/Fifteen_puzzle:

Инвариант - это четность перестановки всех 16 квадратов (15 частей плюс пустой квадрат) плюс четность расстояния такси, перемещаемого пустым квадратом.

Это инвариант, потому что каждый ход изменяетсяи четность перестановки и четность расстояния такси.В частности, если пустой квадрат не перемещается, перестановка оставшихся фигур должна быть четной.

Чтобы рассчитать это соотношение, проверьте http://en.wikipedia.org/wiki/Parity_of_a_permutation (вы также можете проверить Леви-ЧивитаСимвол, но это немного загадочно), внедрите его в python, затем вычислите манхэттенское расстояние, на которое пустой квадрат сдвинулся от своей начальной позиции, и определите сумму обоих этих значений.

Что-то вроде:

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

Если ваш алгоритм действительно не заботится о том, является ли позициявозможно или нет (вы просто делаете это, чтобы сказать «неверный ввод! позиция невозможна!», вы можете проигнорировать эту часть, запустить ее в любом случае в течение нескольких сотен итераций и вернуть «невозможно!», если не решено.

Answer 2

Из-за «циклов», необходимых для перемещения фигур в одной из этих головоломок, обмен частями не может быть сделан изолированно.Рассмотрим доску:

Вы должны поменять местами (11) и (12), чтобы решить ее.Но как ты можешь?Простое «зацикливание» (11, 12, 15, -) в любом направлении никогда не изменит порядок.Поэтому мы должны задействовать больше частей, но при этом мы не можем сохранить порядок этих других частей.Все, что мы попробуем, приведет к порядку замены другой пары.Например, мы можем исправить (11) и (12), используя (7) и (8), но при этом поменять местами (8) и (-):

Таким образом, количество перестановок, необходимых для решения головоломки, должно быть четным, или мы остаемся с «нечетным человеком», как на доске выше.

Поэтому, если вы обнаружите вРешив ситуацию, в которой один своп решит головоломку, вы знаете, что эта доска не может быть решена.