Posts /

Algo #7: Next Lexicographical Permutation

4 mins read ●
Twitter Facebook Google+
07 Sep 2017

Permutation

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

Next Permutation

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:

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

Example

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.

Next Permutation Animation  
Visual arrangement of all possible permutations.

Code

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+