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.
Consider you have
34521 and you need to find its next permutation.
Find the longest decreasing sequence:
Pivot Value: 4
Swap pivot with the smallest value in the sequence which is larger than pivot:
4 swapped with
421 changes to
And put it at its place in the original sequence, we have the next permutation:
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