Last active
October 26, 2016 04:55
-
-
Save vitapluvia/3ced8b4a6d0e4143ac1b145ed64cd33a to your computer and use it in GitHub Desktop.
Permutations in Lexicographic Order
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/env python | |
| import math | |
| import sys | |
| # Based on Narayana Pandita's Algorithm | |
| # ===================================== | |
| # - Find the largest index k such that ar[k] < ar[k + 1]. If no such index exists, the permutation is the last permutation. | |
| # - Find the largest index l greater than k such that ar[k] < ar[l]. | |
| # - Swap the value of ar[k] with that of ar[l]. | |
| # - Reverse the sequence from ar[k + 1] up to and including the final element ar[n]. | |
| def findMaxIndex(ar, i): | |
| for x in range(len(ar) - 1, i - 1, -1): | |
| if ar[x] > ar[i]: | |
| break | |
| return x | |
| def nextLexicographic(ar): | |
| maxK = -1 | |
| for k in range(0, len(ar)-1): | |
| if ar[k] < ar[k + 1]: | |
| maxK = k | |
| if maxK != -1: | |
| maxN = findMaxIndex(ar, maxK) | |
| if maxN != maxK: | |
| ar[maxK], ar[maxN] = ar[maxN], ar[maxK] | |
| last = ar[maxK + 1:] | |
| ar = ar[:maxK + 1] + last[::-1] | |
| return ar | |
| def permutations(s): | |
| values = [] | |
| s = sorted(s) | |
| a = [x for x in s] | |
| values.append(''.join(a)) | |
| for x in range(math.factorial(len(a)) - 1): | |
| a = nextLexicographic(a) | |
| values.append(''.join(a)) | |
| return values |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment