07 Sep 2017

- In Mathematics,
- the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called
**permuting**. –Wikipedia

Today, I’m taking a trip downstream to introduce you to the amazing world of Mathematics where all that boring Algebra and whatnot is actually useful.

I assume that you are familiar with the idea of Permutation. The possible arrangements in a permutation are used in assigning telephone numbers, codes, and other amazing things in telecommunication that I don’t know about. The importance of this little method of arranging numbers and alphabets can be realized from the fact that C++ has a function `next_permutation`

in its standard library.

So, in this post you’ll get to know how to get the next permutation in lexicographic order using a bunch of loops and variables. First, understand the rules:

- In the given sequence, find the longest
*decreasing sequence*(left to right) - Let the value just before the decreasing sequence be the
*pivot* - Now, swap pivot with the smallest value from chosen sequence which is
*larger*than pivot value - Invert the chosen sequence while keeping its place and other values unchanged

If the next permutation is not possible, return false OR the sequence itself, unchanged.

Consider you have `34521`

and you need to find its next permutation.

**Step 1**

Find the longest decreasing sequence: `521`

**Step 2**

Pivot Value: **4**

**Step 3**

Swap pivot with the smallest value in the sequence which is larger than pivot: `35421`

, `4`

swapped with `5`

**Step 4**

Reverse Sequence: `421`

changes to `124`

And put it at its place in the original sequence, we have the next permutation: `35124`

This animation arranges the lines in every possible lexicographical order. It is worth noting that with large sequence, the number of possible permutations can be in multiples of hundred thousand.

```
def _next( current ):
n = len(current) # size
for i in reversed(range(n-1)):
if current[i] < current[i+1]: # get pivot value if sequence breaks
'''Consider this, if we see from right to left, the sub-sequence that we need to find is now increasing sequence.
But the pivot value is that when the sequence shifts to a decreasing one, this is how I found pivot value'''
break # here the pivot is at i
else: # last permutation
return current
# working with the sub-sequence
for j in reversed(range(i, n)):
'''Now, the sub-sequence is an increasing sequence (from right to left, see the 'reversed' keyword), and
the pivot is where sequence becomes decreasing. If I scan form right, the first value that is larger than
pivot is the one I need, because of the order. Numbers do wonders!'''
if current[i] < current[j]:
print ("Value to swap: ", current [j])
# swap
current[i], current[j] = current[j], current[i]
# attach the reversed sub-sequence
current[i + 1:] = reversed(current[i + 1:])
return current
```

See the results in this IPython Notebook. In case of any errors, open an issue in 100 Algorithms repo OR comment below.

You may also like...

Twitter Facebook Google+