CODEWITHSUNDEEP
javascriptarraysfunctionrecursionparameters
Marc
Marc

Reputation: 33

JavaScript function that returns all permutations

I've been trying to make a function that generates all the permutations of the numbers from 0 to num and stores them in a multidimensional array. I want to store in the combinations variable something like:

 [ [ 1, 2, 3 ],
    [ 1, 3, 2 ],
    [ 2, 1, 3 ],
    [ 3, 1, 2 ],
wrongly     [ 2, 3, 1 ],
    [ 3, 2, 1 ] ]

but instead I get:

[ [ 3, 2, 1 ],
  [ 3, 2, 1 ],
  [ 3, 2, 1 ],
  [ 3, 2, 1 ],
  [ 3, 2, 1 ],
  [ 3, 2, 1 ] ]

My function is:

var combinations = [];

function comb(num, index, list, used) {
  if (num == index)
    combinations.push(list);
  else {
    for (var i = 0; i < num; ++i) {
      if (!used[i]) {
        list[i] = index + 1;
        used[i] = true;
        comb(num, index + 1, list, used);
        used[i] = false;
      }
    }
  }
}

I usually program with C++, so I think that I am using the arrays wrongly.

Upvotes: 2

Views: 71

Answers (1)

Nick Parsons
Nick Parsons

Reputation: 50914

Your issue is that the list array you pass into your recursive call is going to be changed as it is essentially passed by reference, so list will lose its previous combinations. Instead, you can make a copy of the array before you pass it into your recursive call using the spread syntax (...).

See working example below:

var combinations = [];

function comb(num, index, list, used) {
  if (num == index)
    combinations.push(list);
  else {
    for (var i = 0; i < num; ++i) {
      if (!used[i]) {
        list[i] = index + 1;
        used[i] = true;
        comb(num, index + 1, [...list], used);
        used[i] = false;
      }
    }
  }
}

comb(3, 0, [], []);
console.log(combinations); // [[1,2,3],[1,3,2],[2,1,3],[3,1,2],[2,3,1],[3,2,1]]
.as-console-wrapper { max-height: 100% !important; top: 0;}

Upvotes: 3

Related Questions