half_permute 全排列

# hail_permte返回全排列组合，但只返回一半，另一半为已返回的反向排列
#
setup = '''\
def half_permute(seq):
    halfPerms = [seq.pop()+seq.pop()] # halfPerms = [seq.pop()] → all_permute
                                      # 替换代码后,得到完整的排列组合
    while seq:
        item = seq.pop()
        tmpPerms = []
        for perm in halfPerms:
            for index in range(len(perm)+1):
                tmpPerms.append(''.join([perm[:index], item, perm[index:]]))
        halfPerms = tmpPerms
    return halfPerms
'''

statement = '''\
numList = list("01234")
permList = half_permute(numList)
permList.sort()
print permList
print len(permList)
'''

import timeit
t = timeit.Timer(statement, setup)
print min(t.repeat(1, 1))
raw_input()