A permutations puzzle

wikimedia

I wrote a very simple game in PyObjC---it's a "fifteen" puzzle. The goal of the game is to get all 15 tiles in order with the empty space in the lower right hand corner. This can be viewed as the permutation:

1, 2, 3 .. 13, 14, 15, 0

I had a vague recollection that some such puzzles are unsolvable, and it's fairly easy to see by just playing that one cannot achieve this order using the standard layout:

1, 2, 3 .. 13, 15, 14, 0

And conversely, if you were presented with the modified layout, the puzzle would not be solvable. Since it seems really important not to give the user an unsolvable puzzle, I looked into it some more and found that permutations (which is what this problem is about) have parity.

Suppose we take the following permutation of 1..5:

3 4 5 2 1

How many swaps (u,v = v,u) does it take to put the numbers into ascending order? This sequence of three works:

(13)(35)(24)

So we can think of this permutation of the sequence as having an odd parity. One question I don't know the answer to is how you would prove that there does not exist some longer sequence of swaps that also reaches the "correct" order, but has even parity. Probably, if I studied the article it is explained there.

A second measure I saw for parity is to take each member of the sequence in turn and compare it with all the members at a higher index:

for i in range(len(L)-1): for j in range(i,len(L)): if L[i] > L[j]: count += 1

We count +1 if the ith element is out of (ascending) order with respect to the jth element, and define the total count of such mismatched pairs as a different measure of parity.

This is the output from such an analysis on all permutations of the sequence 0, 1, 2, 3, showing the permutation, then the results of the swap test, followed by the order test:

0 1 2 3 0 0 0 1 3 2 1 1 0 2 1 3 1 1 0 2 3 1 2 2 0 3 1 2 2 2 0 3 2 1 1 3 1 0 2 3 1 1 1 0 3 2 2 2 1 2 0 3 2 2 1 2 3 0 3 3 1 3 0 2 3 3 1 3 2 0 2 4 2 0 1 3 2 2 2 0 3 1 3 3 2 1 0 3 1 3 2 1 3 0 2 4 2 3 0 1 2 4 2 3 1 0 3 5 3 0 1 2 3 3 3 0 2 1 2 4 3 1 0 2 2 4 3 1 2 0 1 5 3 2 0 1 3 5 3 2 1 0 2 6

The number of swaps required to achieve sorted order is never more than 3, while the reverse order has a maximum of 6 comparisons giving an incorrect order. I notice that these two measures seem to be either both odd or both even, and confirmed that result by testing all permutations of range(10) and random samples from range(25).

Looking ahead, the idea will be that the moves in the puzzle, and particularly those which really matter (vertical ones), don't change the parity, but so far I am not getting the expected answer with that.

from itertools import permutations as perms import random def format(pL): m = len(str(max(pL))) pL = [str(n).rjust(m) for n in pL] return ' '.join(pL) def swaps_to_sort(L,refL=None,verbose=False): if not refL: refL = sorted(L) count = 0 for i in range(len(L)-1): u = L[i] v = refL[i] if verbose: print 'check:', u, if u == v: if verbose: print continue count += 1 j = L.index(v) if verbose: print 'switch ', ':', u, v L[i],L[j] = L[j],L[i] if verbose: list_print(L) return count def out_of_order(L): count = 0 for i,c1 in enumerate(L): for c2 in L[i+1:]: if c1 > c2: count += 1 return count def test1(n): L = perms(range(n)) for p in L: pL = list(p) s = swaps_to_sort(pL[:]) o = out_of_order(pL) print '%s %s %s' % (format(p), s, o) assert s % 2 == o % 2 def test2(): pL = range(25) for i in range(100): random.shuffle(pL) print format(pL) s = swaps_to_sort(pL[:]) o = out_of_order(pL) assert s % 2 == o % 2 test1(4) #test2()