Javascript Heap的算法（非递归）

Question

我在JavaScript实现了Heap的非递归算法。使用 console.log(arr) 检查排列时，一切都按预期工作。但是当我尝试将每个排列推送到结果数组时，一切都会崩溃。它只是 returns 结果填充了最后一次迭代排列。

function generate(n, arr) {
 function swap(item1, item2){
  console.log(item1, item2);
  let tmp = arr[item1];
  arr[item1] = arr[item2];
  arr[item2] = tmp;
 }
 var c = [];
 var allPermutations = [];
 
 for (let i = 0; i < n; i++) {
  c[i] = 0;
 }
 
 console.log(arr);
 allPermutations.push(arr);
 
 for (let i = 1; i < n; i) {
  if (c[i] < i) {
   if (i % 2 == 0) {
    swap(0, i);
   } else {
    swap(c[i], i);
   }
   
   console.log(arr);
   allPermutations.push(arr);
   
   c[i] += 1;
   i = 1;
  } else {
   c[i] = 0;
   i += 1;
  }
 }
 
 return allPermutations;
}

console.log('result', generate(3, ["a", "a", "b"]));

Answer 1

问题是数组只是引用，所以当你推入数组时，你只是在推一个对它的引用。因此，在下一次迭代中更新数组，当您查看最终输出时，所有索引都将相同，因为它是同一个数组。

那你能做什么？克隆它。

allPermutations.push(arr.slice(0));

Answer 2

是的 - 这是一个参考问题。 epascarello 的替代答案：

allPermutations.push([...arr]);

Javascript Heap的算法（非递归）

Javascript Heap's algorithm (non-recursive)

javascript

heaps-algorithm