String Permutations.md

String Permutations

Prompt

Given a string, return an array of all the permutations of that string. The permutations of the string should be the same length as the original string (i.e. use each letter in the string exactly once) but do not need to be actual words. As a reminder, a permutation of a string is another string containing all characters of the original string arranged in a different order.

The array that is returned should only contain unique values

Examples

stringPermutations('one') // ===> [ 'eno', 'eon' 'neo', 'noe', 'oen', 'one']
stringPermutations('app') // ===> [ 'app','pap','ppa']
stringPermutations('nn') // ===> [ 'nn' ]

Solutions

In general we're stuck with O(n!) (factorial) time and space complexity (where n is the number of unique characters in the string). Frankly, the end result of the algorithm demands it, because for n possible characters, it turns out there are n! permutations of those characters.

For generating all possible permutations we could imagine doing so "position by position". There are n possible characters for the first position in the string. Each of those possibilities has n-1 possibilities for the second position (i.e. excluding the character we put in the first position). In turn each of those possibilities has n-2 possibilities for the third position (i.e. excluding the two characters already used for the first two positions). This continues until we reach the last character, which actually just has 1 possibility, because we will have used all other characters at that point. So n possibilities times n-1 possibilities times n-2 possibilities until we reach 1—that is exactly what n! is! You may find an explanation that is figuratively and literally more drawn out here.

So one important lesson to take from this exercise: permutations problems will tend to be factorial time and space complexity.

---

Iterative

const stringPermutations = string => {

  const letters = string.split('')
  let permutations = []

  //add first letter (as an array) to permutations
  permutations.push([letters.shift()])

  while (letters.length) {
  
    const currLetter = letters.shift()
    const tempPermutations = []

    permutations.forEach(perm => {
      for (let i = 0; i <= perm.length; i++) {
      
        //make copy so we can modify it
        const temp = perm.slice() 
        
        //insert the letter at the current position
        temp.splice(i, 0, currLetter)
        
        tempPermutations.push(temp)
      }
    })

    //overwrite the previous results
    permutations = tempPermutations
  }

  return permutations
    .map(letterArr => {
      // convert the letter arrays back to strings
      return letterArr.join('')
    })
    .filter(function(el, idx, self) {
      //filter out non-unique words
      return self.indexOf(el) === idx
    })
}

---

Recursive

const getPerms = (str, arr, permutations) => {

  //on first call, split the string into an array
  if (typeof str === 'string') {
    str = str.split('')
  }

  //base case: push the compiled permutations into the permutations array
  if (!str.length) {
    permutations.push(arr.join(''))
  }
    
  for (let i = 0; i < str.length; i++) {

    const letter = str.splice(i, 1)
    arr.push(letter)

    //recursive call
    getPerms(str, arr, permutations)

    arr.pop()
    str.splice(i, 0, letter)
  }
}

const recursiveStringPermutations = string => {

  const permutations = []

  getPerms(string, [], permutations)

  return permutations
    .filter((el, index) => {
      //filter out non-unique words
      return permutations.indexOf(el) === index
    })
}

Resources

• REPL
• String Permutation In Depth Walkthrough
• Video Solution