Permutations with repetition using recursion - Jav

问题:

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

回答1:

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. You are not keeping variable names consistent: holdingArray vs holdingArr.
2. You never actually push anything into singleSolution.

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

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.