compute_all_permutations_unique_chars.py

#!/usr/bin/python

# Date: 2018-08-04
#
# Description:
# Write a method to compute all permutations of a string of unique characters.
#
# Approach:
# Permutations for n chars can be generated by inserting nth character at all
# positions of all permutations generated by n - 1 chars.
# Like permutation of "a" => ["a"] so permutations of "ab" can be generated by
# inserting "b" at all positions of permutations generated by "a" i.e ["a"] so
# permutations of "ab" => ["ab", "ba"], we inserted "b" at 0 and 1st position.
# Similarly for "abc" we can use permutations of "ab".
# "ab" => ["ab", "ba"]
# "abc" => {c} + ["ab"] => {c} + ["ba"]
# {c} + ["ab"] => ["cab", "acb", "abc"]
# {c} + ["ba"] => ["cba", "bca", "bac"]
#
# {} indicates insert this character at all positions.
#
# Complexity:
# O(n^2 * n!)

def insertAtPosition(string, char, pos):
  """Inserts a character at given position in string.
  
  Args:
    string: Given string.
    char: Character to be inserted.
    pos: Position where char needs to be inserted.
  """
  return string[:pos] + char + string[pos:]

def computePermutationsUniqueChars(string):
  """Generates list of all permutations of a given string.
  
  Args:
    string: Input string.
  """
  if not len(string):
    return []
  elif len(string) == 1:
    return [string]

  permutations = []
  first = string[0]
  remainder = string[1:]
  words = computePermutationsUniqueChars(remainder)
  for word in words:
    for idx in range(len(word) + 1):  # Insert all positions so +1 used.
      s = insertAtPosition(word, first, idx)
      permutations.append(s)
  return permutations

def main():
  string = input('Enter input string(having unique characters): ')
  permutations = computePermutationsUniqueChars(string)
  for idx in range(len(permutations)):
    print('{idx}: {perm}'.format(idx=idx + 1, perm=permutations[idx]))

if __name__ == '__main__':
  main()