# Day 3: Next permutation

Given a totally ordered set, find the next permutation of the current configuration: `FADE -> FAED -> FDAE -> FDEA -> ...`

Even though almost every library offers a similar function, this tool can quickly become very useful in various competitions when you need to speed your algorithm up.

The algorithm itself is simple. Beginning from end, find the longest decreasing sequence `42`

and denote the preceding item as pivot **531**`4`

. Swap pivot with the smallest higher item **2**531`4`

in the sequence and revert the sequence **3**5**2**1`43`

.**125**

#### algorithm

https://github.com/coells/100days

def permute(values):

n = len(values)

# i: position of pivot

for i in reversed(range(n - 1)):

if values[i] < values[i + 1]:

break

else:

# very last permutation

values[:] = reversed(values[:])

return values

# j: position of the next candidate

for j in reversed(range(i, n)):

if values[i] < values[j]:

# swap pivot and reverse the tail

values[i], values[j] = values[j], values[i]

values[i + 1:] = reversed(values[i + 1:])

break

return values

#### test

> permute(list('FADE'))

['F', 'A', 'E', 'D']