Next permutation即排列的下一个,比如数字1,2,3的排列有
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
那么2,3,1的next permutation就是3,1,2。
以下这个程序完全是用来晕人的,实现的方法效率并不高。不过既然是晕人用的,我就不具体解释它的原理了,呵呵。
def next(a):
try:
i = [k for k in range(-2, -len(a)-1, -1) if a[k]<a[k+1]][0]
j = [k for k in range(-1, i, -1) if a[i]<a[k]][0]
return a[:i] + [a[j]] + a[-1:j:-1] + [a[i]] + a[j-1:i:-1]
except:
return None
a = [1, 2, 3, 4, 5]
while a:
print a
a = next(a)