## 线性时间计算排列的奇偶性¶

### 计算交换次数（鸠占鹊巢）¶

• 鸠现在占着鹊(Magpie)巢
• 鸠的巢(nest)被麻雀(sparrow)占领
• 鸠和麻雀换巢：鸠回到自己的巢，麻雀挪到鹊的巢
In [1]:
def rev_index(l):
'''Construct nest<->bird reversed index'''
rev=empty_like(l)
for i, j in enumerate(l):
rev[j]=i
return rev
def count_swap(nest2bird, bird2nest):
'''Count swaps needed by an order'''
count=0
for dove, magpie in enumerate(bird2nest):
if dove!=magpie:
count+=1
sparrow=nest2bird[dove]
nest2bird[magpie]=sparrow
bird2nest[sparrow]=magpie
return count


## 根据奇偶性判断拼图的可解性¶

In [2]:
def isSolvable(puzzle):
'''Judge solvability of 2D matrix A,
with largest elem representing empty O'''
m,n = puzzle.shape
empty = puzzle.size - 1
nest2bird = puzzle.flatten()
bird2nest = rev_index(nest2bird)
ds=sum(divmod(empty - bird2nest[empty], n))
cnt=count_swap(nest2bird, bird2nest)
return (cnt+ds)%2 == 0


## 生成拼图¶

In [3]:
def puzzle(m, n=None, shufall=True):
if not n:
n=m
if (n<2 or m<2):
raise Exception('Puzzle too small')
A=arange(m*n)
if shufall:
shuffle(A)
else:
shuffle(A[:-1])
A=A.reshape([m,n])
if not isSolvable(A):
if A[0,0] != A.size-1 and A[0,1] != A.size-1:
A[0,0],A[0,1]=A[0,1],A[0,0]
else:
A[1,0],A[1,1]=A[1,1],A[1,0]
return A


## 生成的例子¶

In [4]:
puzzle(6, shufall=False) # 最后一个格子不变

Out[4]:
array([[30,  6,  0,  4, 21,  9],
[ 3, 25, 18, 17, 24, 34],
[12, 10, 29,  5, 32, 22],
[27, 13, 23, 26, 16, 15],
[19,  2,  1, 11, 33,  8],
[28,  7, 20, 14, 31, 35]])
In [5]:
puzzle(6) # 最后一个格子位置随机

Out[5]:
array([[ 9, 15, 25, 34, 13, 22],
[28, 26, 19,  8, 12, 35],
[16, 21, 33,  0, 27, 17],
[ 1, 24, 23,  6, 29,  5],
[10,  2,  4,  7, 14, 20],
[30, 32, 18, 31, 11,  3]])