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

计算交换次数(鸠占鹊巢)

扫描所有的鸟,命名为鸠(Dove):

  • 鸠现在占着鹊(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]])

Comments

comments powered by Disqus