为什么JavaScript实现的Heap全排列算法将结果存入数组不生效
问题原因
- 数组在JavaScript中属于引用数据类型,你直接执行
count.push(a)时,实际存入count的是数组a的内存地址引用,而非当前时刻a的快照值。 - Heap算法执行过程中会持续修改原数组
a的元素顺序,所有存入count的引用都指向同一个数组对象,最终打印时展示的都是数组修改完成后的最终值,才会出现全部元素相同的错误结果。 - 你直接用
console.log(a)能正常输出的原因是:控制台打印时会立刻输出当前数组的瞬时值,不会受后续数组修改的影响。
解决方法
只需要在存入结果数组时,对当前的a做一次浅拷贝即可,常见的拷贝方法可以用[...a]扩展运算符、a.slice()、Array.from(a)都可以。
另外原有代码还有两处小问题可以顺便修正:
- 第一个示例代码中递归调用
per(a, size-1;漏写了右括号 - 函数没有显式接收结果数组参数,用全局变量
count的写法不够稳妥,建议调整成参数传递的形式
修正后的完整代码
function per(a, size, result) { if (size === 1) { // 存入当前数组的拷贝,而非原引用 result.push([...a]); return; } for (let i = 0; i < size; i++) { per(a, size - 1, result); if (size % 2 === 1) { // 奇数长度交换第一个和最后一个元素 [a[0], a[size - 1]] = [a[size - 1], a[0]]; } else { // 偶数长度交换当前遍历位置和最后一个元素 [a[i], a[size - 1]] = [a[size - 1], a[i]]; } } } const result = []; const arr = [1, 2, 3]; per(arr, arr.length, result); console.log(result);
正确输出结果
[ [ 1, 2, 3 ], [ 2, 1, 3 ], [ 3, 1, 2 ], [ 1, 3, 2 ], [ 2, 3, 1 ], [ 3, 2, 1 ] ]
内容的提问来源于stack exchange,提问作者Nayla
相关产品推荐
相关产品推荐

