Javascript Heap's algorithm (non-recursive)

Question

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"]));

You cannot be bother to cut'n'paste the code. I cannot be bothered to follow the link — Ed Heal
– Ed Heal, Commented Sep 22, 2016 at 20:29
@rubylifequestions Stackoverflow has snipplets that run... and if someone wants to play, they push a button and it is copied to an answer. — epascarello
– epascarello, Commented Sep 22, 2016 at 20:31

epascarello · Accepted Answer · 2016-09-22 23:24:29Z

1

The problem is that arrays are just references so when you push in the array you are just pushing a reference to it. So, on the next iteration you update the array and 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));

edited Sep 22, 2016 at 23:24

user950658

answered Sep 22, 2016 at 20:39

epascarello

208k20 gold badges206 silver badges246 bronze badges

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

Comments

spectrumUser · Accepted Answer · 2020-04-22 21:02:00Z

0

Yep - its a reference problem. Alternative to epascarello's answer:

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

answered Apr 22, 2020 at 21:02

spectrumUser

1

Collectives™ on Stack Overflow

Javascript Heap's algorithm (non-recursive)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related