순열 반전 수 찾기

Question

나는 15 개의 퍼즐 풀버를 만들려고하기 때문에 this을보고있었습니다. 나는 그것이 무엇에 관한 것인지 정말로 이해하지 못한다. "목록의 순열 기호가 +1이면 위치가 가능하다"라는 주어진 숫자 집합 (0-15, 배열에 저장, 0은 공백)이 유효한지 확인하는 방법은 무엇입니까? 그 관련성이 있다면 나는 자바 스크립트에서 일하고있다.

Answer 1

다음을 고려하십시오. 해결 된 15 개의 퍼즐을 가져 와서 한 쌍의 plyers를 물리적으로 제거하고 교체 한 후 14 및 15 블록을 교체하고 스크램블 한 경우 올바른 상태로 되돌릴 수 있습니까?

대답은 전혀 없습니다. 당신이 15 개의 퍼즐에서 할 수있는 모든 움직임에 의해 보존되는 불변성이 있습니다. 순열 기호는 아마도 그 불변성을 나타냅니다. http://en.wikipedia.org/wiki/Fifteen_puzzle 따르면

:

불변은 16 제곱의 순열의 패리티 (15 개 플러스 빈 사각형) 플러스 빈 사각형 택시에 의해 이동 거리의 패리티이다.

이것은 각 이동이 순열의 패리티와 택시 거리의 패리티를 모두 변경하므로 불변합니다. 특히 빈 사각형을 이동하지 않으면 나머지 조각의 순열이 균등해야합니다. 다음 맨해튼 거리를 계산

가 (당신은 또한 레위 - Civita 기호를 체크 아웃 할 수 있지만, 조금 비밀이다) http://en.wikipedia.org/wiki/Parity_of_a_permutation을 확인,이 패리티를 계산하려면, 파이썬에서 구현, 빈 광장의 시작에서 이동 위치를 계산하고 두 값의 합계를 계산합니다. 같은

뭔가 :

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

결과 : 여기

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

은 몇 가지 예/테스트 케이스입니다

| 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

이러한 퍼즐 중 하나에서 조각을 이동하는 데 필요한 "주기"때문에 조각 스왑을 별도로 만들 수 없습니다. 보드를 고려해

당신은이 (12)를 해결하기 위해 (11)을 교체해야합니다. 하지만 어떻게 할 수 있니? 어느 방향 으로든 단순히 "사이클링"(11, 12, 15, -)하면 순서가 변경되지 않습니다. 그러므로 우리는 더 많은 조각을 포함시켜야하지만 그렇게하면 다른 조각의 순서를 유지할 수 없습니다. 우리가 시도하는 어떤 것이라도 다른 쌍의 순서가 바뀌게됩니다.예를 들어, 우리는 포함하여 (12) (11)과를 해결 수있는 (7), (8),하지만 그렇게함으로써, 교환 제 (8)와 (-) :

따라서

, 퍼즐을 풀기 위해 필요한 스왑의 수는 일정해야합니다. 그렇지 않으면 위의 보드에서와 같이 "이상한 남자"가 남았습니다.

다시 말해, 해결사에서 단일 스왑이 퍼즐을 푸는 상황을 발견하면이 보드를 해결할 수 없다는 것을 알고 있습니다.