Permutations with repetition using recursion - JavaScript

Question

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

score 11 · Accepted Answer · 2015-05-20 05:06:51Z

11

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:

You are not keeping variable names consistent: holdingArray vs holdingArr.
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.

edited May 20, 2015 at 5:06

answered May 20, 2015 at 4:47

user4918798

Sign up to request clarification or add additional context in comments.

1 Comment

zahabba Over a year ago

Thank you. #1 was just a transcription typo (fixed). #2 is a good question...not sure what (and where) I should be pushing into singleSolution...And sorry I wasn't clearer but I am looking for a working implementation that uses recursion.

Collectives™ on Stack Overflow

Permutations with repetition using recursion - JavaScript

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related