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 42531 and denote the preceding item as pivot 42531. Swap pivot with the smallest higher item 43521 in the sequence and revert the sequence 43125.


def permute(values):
n = len(values)

# i: position of pivot
for i in reversed(range(n - 1)):
if values[i] < values[i + 1]:
# 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:])

return values


> permute(list('FADE'))
['F', 'A', 'E', 'D']
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.