Permutation with Backtracking in React.js – 以回溯算法演示排列问题,React.js 呈现

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);
      }, []);
  };

Credits