Функция JavaScript, которая возвращает все перестановки

Question

Я пытался создать функцию, которая генерирует все перестановки чисел от 0 до num и сохраняет их в многомерном массиве. Я хочу хранить в переменной комбинации что-то вроде:

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

но вместо этого я получаю:

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

Моя функция:

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

Я обычно программирую на C ++, поэтому считаю, что я использую массивы неправильно.

Answer 1

Ваша проблема в том, что массив list, который вы передаете в рекурсивный вызов, будет изменен, поскольку он по существу передается по ссылке, поэтому list потеряет свои предыдущие комбинации.Вместо этого вы можете сделать копию массива, прежде чем передать его в рекурсивный вызов, используя синтаксис распространения (...).

См. Рабочий пример ниже:

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