# Next Permutation

Posted on Fri 24 March 2017 in Puzzles

Aim: Find a larger permutation

We must move a larger number forward. So we should go from the tail to find any new number is smaller than a number behind it. If no next permutation, reverse list.

In [ ]:
def next_permutation(l):
'''Give out the next permutation of list l
>>> next_permutation([2, 1, 3])
[2, 3, 1]
>>> next_permutation([3, 2, 1])
[1, 2, 3]
'''
n=len(l)
for i in range(n-2, -1, -1):
if l[i]<l[i+1]:
for j in range(n-1, i, -1):
if l[j]>l[i]:
l[j],l[i]=l[i],l[j]
l[i+1:]=l[n-1:i:-1]
return l
return l[::-1]


## Peumutation Loop until reoccurance¶

In [ ]:
def permu_circ(l):
'''Loop over permutations until goes back to initial permutation given by list l
>>> for k in permu_circ([2,1,3]): print(k)
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
[1, 2, 3]
[1, 3, 2]
'''
assert(isinstance(l, list))
ini=l.copy()
while True:
yield l
l=next_permutation(l)
if l==ini:
break
return


## Permutation of 1 to n¶

It is inefficient for all permutations in this way

In [3]:
def permu_num(n):
'''Permutations over 1, 2,..., n
>>> for k in permu_num(3): print(k)
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
'''
return permu_circ(list(range(1,n+1)))
if __name__=='__main__':
import doctest
doctest.testmod()