使用递归的重复排列-JavaScript [英] Permutations with repetition using recursion - JavaScript

问题描述

我正在研究一种递归算法，该算法采用具有三个不同元素的数组(例如['a', 'b', 'c']，并返回一个二维数组，其中所有可能的变化都允许重复(所以[['a', 'a', 'a'], ['a', 'a', 'b'], ['a', 'b', 'b'],...]).但是我的代码失败，我不确定为什么.

I'm working on a recursive algorithm that takes in an array with three different elements (say ['a', 'b', 'c'] and returns a two-dimensional array with all the possible variations with repetition allowed (so [['a', 'a', 'a'], ['a', 'a', 'b'], ['a', 'b', 'b'],...]). However my code fails and I'm not sure why.

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;
};

推荐答案

我假设您不是在寻找完整的工作实现，而是代码中的错误.这是我发现的一些东西:

I'm assuming that you're not looking for a complete working implementation but rather the errors in your code. Here are some I found:

1. 您没有使变量名保持一致:holdingArray vs holdingArr.
2. 您从未真正将任何东西推入singleSolution.

1. You are not keeping variable names consistent: holdingArray vs holdingArr.
2. You never actually push anything into singleSolution.

这是一个有效的实现，基于您的原始代码.

Here's a working implementation, based on your original code.

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副本上工作，而不是在闭包范围内保持相同.而且，由于到目前为止，我们都在遍历选项而不是解决方案，因此无需让递归函数将选项作为参数.

You basically want each recursive function call to work on its own copy of singleSolution, rather than keeping a common one in closure scope. And, since we are iterating over the options rather than the solution so far, there is no need to have the recursive function take the options as a parameter.

这篇关于使用递归的重复排列-JavaScript的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！