a solve to http://www.zhihu.com/question/20467075

lovers.py

#!/usr/bin/env python
# a solve to http://www.zhihu.com/question/20467075
import random

def gen_seats(n):
    ls = range(1, n + 1) * 2
    random.shuffle(ls)
    return ls

def get_strategies(ls):
    if ls == []:
        return []

    x, y = ls[:2]
    nls = ls[2:]
    if nls == [] or x == y:
        swap_strategy = 0
    else:
        yi = nls.index(y)
        xi = nls.index(x)

        if x == ( nls[yi - 1] if yi % 2 else nls[yi + 1] ):
            # has double effect when swapping x
            swap_strategy = 1
            nls[yi] = x
        else:
            swap_strategy = 2
            nls[xi] = y

    return [ swap_strategy ] + get_strategies(nls)

def show_steps(ls, ss):
    if ss == []:
        return
    
    s, nss = ss[0], ss[1:]
    x, y = ls[:2]
    nls = ls[2:]

    if s == 1:
        yi = nls.index(y)
        nls[yi] = x
    elif s == 2:
        xi = nls.index(x)
        nls[xi] = y

    if s != 0:
        print ' '.join(map(str, nls))
    return show_steps(nls, nss)

def count_steps(ss):
    return len([s for s in ss if s])

if __name__ == "__main__":
    import sys

    try:
        n = int(sys.argv[1])
    except:
        n = 10
    seats = gen_seats(n)
    ss = get_strategies(seats)

    print ' '.join(map(str, seats))
    show_steps(seats, ss)
    print "n = %d, steps = %d" % (n, count_steps(ss))