Skip to content

Instantly share code, notes, and snippets.

@jewelsjacobs
Created July 6, 2022 10:14
Show Gist options
  • Save jewelsjacobs/f8897a8233a8aabf4ee760c1323b2a2d to your computer and use it in GitHub Desktop.
Save jewelsjacobs/f8897a8233a8aabf4ee760c1323b2a2d to your computer and use it in GitHub Desktop.
Get Permutations Algo Recursion - I don't get it help
// Without Repetitions
function getPermutations(options) {
const permutations = []
console.log("FN START")
console.log(options)
if (options.length === 1) {
return [options] // return statement doesn't seem to break out of function why?
}
const partialPermutations = getPermutations(options.slice(1)) // this seems to get skipped after return statement on line 9
console.log("AFTER RECURSIVE STEP") // but then we go here why?
console.log(partialPermutations)
const firstOption = options[0]
console.log("FIRST OPTION")
console.log(firstOption)
for (let i = 0; i < partialPermutations.length; i++) {
const partialPermutation = partialPermutations[i]
console.log("OUTER LOOP")
console.log(partialPermutation)
for (let j = 0; j <= partialPermutation.length; j++) {
const permutationInFront = partialPermutation.slice(0, j)
const permutationAfter = partialPermutation.slice(j)
permutations.push(
permutationInFront.concat([firstOption], permutationAfter)
)
}
}
return permutations
}
const todoListItems = [
"walk the dog",
"clean the toilet",
"buy groceries",
"order food",
"do homework"
]
console.log(getPermutations(todoListItems))
// Time Complexity: O(n!) => 4 * 3 * 2 * 1 = 24; 5 * 4 * 3 * 2 * 1 = 120
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment