Skip to content

Instantly share code, notes, and snippets.

@porteron

porteron/permutations.js

Created July 30, 2019 05:15
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save porteron/0939289d1c60467d6fc13d6cb87bebc0 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save porteron/0939289d1c60467d6fc13d6cb87bebc0 to your computer and use it in GitHub Desktop.
Download ZIP
Find all permutations of a string.
Raw
permutations.js
function permutations(word){
if(word.length <=1) return [word];
if(typeof word === 'string'){
word = word.split('')
}
if(typeof word === 'number'){
word = String(word).split('')
}
let permutationCollection = [];
let nextWord = [];
let characters = [];
permute(word);
return permutationCollection
function permute(characters){
if(characters.length < 1){
// add word to permutations array
permutationCollection.push(nextWord.join(''));
}
for(let i = 0; i < characters.length; i++){
characters.push(characters.shift());
nextWord.push(characters[0])
permute(characters.slice(1););
nextWord.pop();
}
}
}
@porteron
Copy link
Author

porteron commented Jul 30, 2019

Find all permutations of a string

Steps:

  1. Create an example
    1. Given the string ‘abc’ , return [abc, bca, cba, etc…]
  2. What data structure will you use?
    1. Probably use an array structure because of easy manipulation
  3. Begin.
    1. Take word input, convert to array, take the first letter of the word and see how many combinations your can make of the remaining slots of the word
    2. Keep track of the current word combinations
      1. Local Variables Needed:
        1. Array to hold all the permutations
        2. Array to hold the characters left that we are iterating over
        3. Array to hold the building up of the next word
    3. Seems like a good use case for recursion, so let’s create a recursive function that will determine the combinations of the next slots
    4. Base condition for the recursive function will be to see if the length of the
    5. Iterate over passed in characters
      1. Rotate the array
      2. Add next letter to nextWord array to keep track
      3. Remove letter from the characters
      4. Call recursively with the same string rotated
      5. Once recursion is complete remove word from nextWord array

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment