ruby life questions ruby life questions - 2 months ago 19
Javascript Question

Javascript Heap's algorithm (non-recursive)

I have implemented Heap's non-recursive algorithm in JavaScript.
When checking permutations with

console.log(arr)
everything works as expected.
But when I try to push each permutation to a result array, then everything breaks up. It just returns result filled with last iteration permutation.


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

The problem is the arrays are just a reference so when you push in the array you are just pushing an a reference to it. So on the next iteration you update the array. So when you look at the final output, all the indexes will be the same since it is the same array.

So what can you do? clone it.

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