Permutations in Lexicographic Order

lexicographic-permutations.py

#!/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