使用递归的重复排列 - JavaScript

Question

我正在研究一种递归算法，该算法接受一个包含三个不同元素的数组（比如 ['a', 'b', 'c'] 和 returns 一个二维数组，其中包含所有可能的变化并允许重复（所以[['a', 'a', 'a'], ['a', 'a', 'b'], ['a', 'b', 'b'],...])。但是我的代码失败了，我不确定为什么。

var abc = function () {
  var holdingArr = [];
  var threeOptions = ["a", "b", "c"];
  var singleSolution = [];  
  var recursiveABC = function(arr) {
      if (singleSolution.length > 2) {
        holdingArr.push(singleSolution);
        singleSolution = [];
        return;
      }
      for (var i=0; i < arr.length; i++) {
        recursiveABC(arr.slice(i+1));
      }
  };
  recursiveABC(threeOptions);
  return holdingArr;
};

Answer 1

我假设您不是在寻找完整的工作实现，而是在寻找代码中的错误。以下是我发现的一些：

您没有保持变量名称一致：holdingArray vs holdingArr.
你从来没有真正将任何东西推入 singleSolution。

编辑：这是一个基于您的原始代码的有效实现。

var abc = function () {
  var holdingArr = [];
  var threeOptions = ["a", "b", "c"];
  var recursiveABC = function(singleSolution) {
      if (singleSolution.length > 2) {
        holdingArr.push(singleSolution);
        return;
      }
      for (var i=0; i < threeOptions.length; i++) {
        recursiveABC(singleSolution.concat([threeOptions[i]]));
      }
  };
  recursiveABC([]);
  return holdingArr;
};

您基本上希望每个递归函数调用都在其自己的 singleSolution 副本上工作，而不是在闭包范围内保留一个公共函数。而且，由于到目前为止我们正在迭代选项而不是解决方案，因此没有必要让递归函数将选项作为参数。

使用递归的重复排列 - JavaScript

Permutations with repetition using recursion - JavaScript

javascript

arrays

algorithm

recursion

permutation