#coding=utf-8
#
#关于这个问题的精彩讨论参见这里
#  http://groups.google.com/group/python-cn/browse_thread/thread/4d9eda8e422a6cf8
#
#猜数字游戏8步以内的求解程序的一部分
#用来生成四位不重复数字(0-9)的所有组合，比如8765, 9876, 0123

#用的是最直接的方法，4重for循环：
#by realfun
def init_set():
    ret = []
    for i in range(0, 10):
        for j in range(0, 10):
            for k in range(0, 10):
                for l in range(0, 10):
                    if i != j and i != k and i != l and j != k and j != l and k != l:
                        ret.append((i, j, k, l))
    return ret

#改进的4重for，减少判断语句被调用的次数
#by Leo Jay
def init_set2():
    ret = []
    for i in range(0, 10):
        for j in range(0, 10):
            if i == j: continue
            for k in range(0, 10):
                if j == k: continue
                for l in range(0, 10):
                    if k == l: continue
                    if i != k and i != l and j != l:
                        ret.append((i, j, k, l))
    return ret

#引入set，消除所有的判断语句
#by realfun
def init_set3():
    s1 = set(range(0, 10))
    ret = []
    for i in s1:
        s2 = s1.copy()
        s2.remove(i)
        for j in s2:
            s3 = s2.copy()
            s3.remove(j)
            for k in s3:
                s4 = s3.copy()
                s4.remove(k)
                for l in s4:
                    ret.append((i, j, k, l))
    return ret

#by Nick Cen
def perm(items, n=None):
    if n is None:
        n = len(items)
    for i in range(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[:i] + items[i+1:]
            for p in perm(rest, n-1):
                yield v + p

#by Nick Cen
#递归的方法消除判断语句
def init_set4():
    ret = []
    for i in perm(range(0,10),4):
        ret.append(i)
    return ret

#展开版，采用init_set3生成，已知程序里面最快的
#灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
#应该不能更快了，因为这个版本已经没有多余的操作了
#by Leo Jay
def init_set5():
    ret = []
    for i in xrange(0, 10):
       for j in xrange(i+1, 10):
           for k in xrange(j+1, 10):
               for l in xrange(k+1, 10):
                   ret.append((i, j, k, l))
                   ret.append((i, j, l, k))
                   ret.append((i, k, j, l))
                   ret.append((i, k, l, j))
                   ret.append((i, l, j, k))
                   ret.append((i, l, k, j))
                   ret.append((j, i, k, l))
                   ret.append((j, i, l, k))
                   ret.append((j, k, i, l))
                   ret.append((j, k, l, i))
                   ret.append((j, l, i, k))
                   ret.append((j, l, k, i))
                   ret.append((k, i, j, l))
                   ret.append((k, i, l, j))
                   ret.append((k, j, i, l))
                   ret.append((k, j, l, i))
                   ret.append((k, l, i, j))
                   ret.append((k, l, j, i))
                   ret.append((l, i, j, k))
                   ret.append((l, i, k, j))
                   ret.append((l, j, i, k))
                   ret.append((l, j, k, i))
                   ret.append((l, k, i, j))
                   ret.append((l, k, j, i))
    return ret

#limodou: 得到一个灵感，可以写一个程序生成的程序，用来生成上面的代码。
#Leo Jay: 嘿嘿，实际上这段代码就是自动生成的
def gen_fun5():
    def init_set3():
       s1 = set(range(0, 4))
       ret = []
       for i in s1:
           s2 = s1.copy()
           s2.remove(i)
           for j in s2:
               s3 = s2.copy()
               s3.remove(j)
               for k in s3:
                   s4 = s3.copy()
                   s4.remove(k)
                   for l in s4:

                       ret.append((i, j, k, l))
       return ret

    c = ['i', 'j', 'k', 'l']
    for i, j, k, l in init_set3():
       print 'ret.append((%s, %s, %s, %s))' % (c[i], c[j], c[k], c[l])
    
#下面的代码用来测试性能
import time

def timing(f, n):
    print f.__name__, n, "times",
    r = range(n)
    t1 = time.clock()
    for i in r:
        f()
    t2 = time.clock()
    print round(t2-t1, 3)

#直接的四重for
timing(init_set, 1000)
#init_set 1000 times 5.624

#四重for里面每层都加入判断，减少不必要的for
timing(init_set2, 1000)
#init_set2 1000 times 4.815

#引入set灭掉所有的判断语句(if语句)
timing(init_set3, 1000)
#init_set3 1000 times 3.189

#用递归灭掉所有的判断语句（递归调用开销大啊）
timing(init_set4, 1000)
#init_set4 1000 times 17.03

#灭掉了所有的判断语句，同时用展开的方法灭掉了set，目前已知最快的
#应该不能更快了，因为这个版本已经没有多余的操作了
timing(init_set5, 1000)
#init_set5 1000 times 2.024