Permutations without Dups

Write a method to compute all permutations of a string of unique characters.

Solution

To build the recursive solution, let’s consider the base case when the string has one element. In this case, we will return the string itself. When the string has two elements, we want to append the second element before and after the first. Our recursion involves computing the permutations for a substring of size n-1, and adding the nth element at every possible location in those substrings.

def permutations(input_str):
  if(len(input_str) == 1):
    return [input_str]

  substrings = permutations(input_str[:-1])
  strings = []

  for string in substrings:
    for i in range(len(string) + 1):
      strings.append(string[:i] + input_str[-1] + string[i:])

  return strings