# Definition(s)

Description of the algorithm for next_permutation:

Find largest index i such that array[i − 1] < array[i]. (If no such i exists, then this is already the last permutation.)

Find largest index j such that j ≥ i and array[j] > array[i − 1].

Swap array[j] and array[i − 1].

Reverse the suffix starting at array[i].

# Algortihm(s)

``````

In [1]:

def next_permutation(perm):
n = len(perm)

# Find longest non-increasing suffix
i = n - 1
while i > 0 and perm[i - 1] >= perm[i]:
i -= 1

# Is this the last permutation?
if i <= 0:
return False

# perm[i - 1] is the pivot
# search for the rightmost j such that perm[j] > perm[i - 1]
j = n - 1
while perm[j] <= perm[i - 1]:
j -= 1

assert j >= i

# perm[j] will become the new pivot (swap perm[i-1] and perm[j])
perm[i - 1], perm[j] = perm[j], perm[i - 1]

# reverse the suffix perm[i..j]
perm[i:j+1] = perm[i:j+1][::-1]

return True

# generator for all permutations
def permutations(perm):
is_next = True

while is_next:
yield perm
is_next = next_permutation(perm)

``````

# Run(s)

``````

In [3]:

p = [1, 3, 2, 4]
print(next_permutation(p), p)

``````
``````

True [1, 3, 4, 2]

``````
``````

In [4]:

p = [2, 4, 3, 7, 6, 8, 9, 5, 1, 0]
print(next_permutation(p), p)

``````
``````

True [2, 4, 3, 7, 6, 9, 8, 5, 1, 0]

``````
``````

In [5]:

for p in permutations(list(range(4))):
print(p)

``````
``````

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 2, 0]
[2, 1, 3, 0]
[2, 3, 1, 0]
[3, 2, 1, 0]

``````
``````

In [6]:

p = ['a', 'l', 'e', 'x']
print(next_permutation(p), p)

``````
``````

True ['a', 'l', 'x', 'e']

``````