क्रमपरिवर्तन inversions की संख्या ढूँढना

Question

मैं this पर देख रहा था क्योंकि मैं एक पंद्रह पहेली हल करने की कोशिश कर रहा हूं। मैं वास्तव में समझ में नहीं आता कि यह किस बारे में बात कर रहा है। मैं जांचने के बारे में कैसे जाउंगा कि संख्याओं का एक निर्धारित सेट (0-15 से, एक सरणी में संग्रहीत, 0 खाली है) मान्य है कि "यदि सूची का क्रमपरिवर्तन प्रतीक +1 है तो स्थिति संभव है"। मैं जावास्क्रिप्ट में काम कर रहा हूं, अगर यह प्रासंगिक है।

Answer 1

पर विचार करें: यदि आप एक हल 15-पहेली ले लिया है, और शारीरिक रूप से हटा दिया और बदली plyers की एक जोड़ी के साथ और 14 और 15 ब्लॉक की जगह है, और यह तले ... आप यह एक वैध स्थिति में लौट सकता है?

जवाब नहीं है। एक ऐसा आविष्कार है जो 15-पहेली में आपके द्वारा किए जा सकने वाले सभी कदमों से संरक्षित है, और क्रमपरिवर्तन प्रतीक शायद उस आविष्कार का जिक्र कर रहा है।

http://en.wikipedia.org/wiki/Fifteen_puzzle के अनुसार:

अपरिवर्तनीय सभी 16 वर्गों के क्रमपरिवर्तन की समता (15 टुकड़े प्लस रिक्त वर्ग) के साथ साथ रिक्त वर्ग द्वारा ले जाया गया टेक्सी दूरी की समता है।

यह एक आविष्कार है क्योंकि प्रत्येक कदम क्रमपरिवर्तन की समानता और टैक्सीकैब दूरी की समानता दोनों को बदलता है। विशेष रूप से यदि खाली वर्ग स्थानांतरित नहीं किया जाता है तो शेष टुकड़ों का क्रमपरिवर्तन भी होना चाहिए।

इस समता की गणना करने के http://en.wikipedia.org/wiki/Parity_of_a_permutation की जाँच (आप भी लेवी के Civita प्रतीक की जाँच सकता है, लेकिन यह थोड़ा रहस्यमय है), अजगर में लागू है, तो मैनहट्टन दूरी की गणना रिक्त वर्ग इसके प्रारंभिक से ले जाया गया है स्थिति, और उन दोनों मूल्यों के योग की समानता ले लो।

कुछ की तरह:

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

इन पहेली में से किसी एक पर टुकड़े को स्थानांतरित करने के लिए आवश्यक "चक्र" की वजह से, टुकड़ा स्वैप अलगाव में नहीं बनाया जा सकता है। बोर्ड पर विचार करें:

आप स्वैप करना होगा (11) एक (12) इसे हल करने की। लेकिन आप कैसे कर सकते हैं किसी भी दिशा में बस "साइकिल चलाना" (11, 12, 15, -) आदेश को कभी नहीं बदलेगा। इसलिए हमें और टुकड़े शामिल करना होगा, लेकिन ऐसा करने में, हम उन अन्य टुकड़ों के क्रम को संरक्षित नहीं कर सकते हैं। जो भी हम कोशिश करते हैं, उसके परिणामस्वरूप दूसरी जोड़ी को बदल दिया जा सकता है।उदाहरण के लिए, हम को शामिल करके सही कर सकता है (11) और (12) (7) और (8) है, लेकिन ऐसा करने में, स्वैप (8) और (-):

इसलिए, पहेली को हल करने के लिए आवश्यक स्वैप की संख्या भी होनी चाहिए, या ऊपर दिए गए बोर्ड में हमें "अजीब आदमी" के साथ छोड़ दिया जाना चाहिए।

इसलिए फिर, यदि आप अपने सॉल्वर में एक ऐसी स्थिति का पता लगाते हैं जिसमें एक स्वैप पहेली को हल करेगा, तो आप जानते हैं कि इस बोर्ड को हल नहीं किया जा सकता है।