Javascript堆's算法(非递归)

Javascript Heap's algorithm (non-recursive)

本文关键字：递归 算法 Javascript      更新时间：2023-09-26

我已经在JavaScript中实现了Heap的非递归算法。当用console.log(arr)检查排列时，一切都如预期的那样工作。但是当我尝试将每个排列推入结果数组时，一切都中断了。它只返回最后一次迭代排列的结果。

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

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

那么你能做什么呢?克隆它。

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

是的，这是一个参考问题。替代epascarello的答案:

allPermutations.push([...arr]);
相关文章：