Motivation
Permutation algorithm is NP-Hard in factorial time complexity. It’s the a step of the naive solutions to solve Travelling Salesman issue.
Code
Analysis
/**
* The algorithm use backtracking approach to list all mutations
*
* The space complexity (stack size) is optimzied to O(h)
* for a M-way tree with reduced degree `M`.
* The `M` is reduced from N to 1; `h == N`
*
*
*/
backtrackingR = currentWordStack => {
if (currentWordStack.length === 1) {
return currentWordStack;
}
return currentWordStack
.map((word, idx) => {
return this.backtrackingR(
currentWordStack.filter((innerWord, innerIdx) => {
// if we return `innerWord !== word`,
// the duplications would be removed
return idx !== innerIdx;
})
).map(childWord => {
return word + childWord;
});
})
.reduce((prev, curr) => {
return prev.concat(curr);
}, []);
};