Ruby backtracking中数组传参不当导致全排列结果异常
问题成因
answer的object_id全程固定是正常现象——这个数组从初始化到递归结束从未被重新赋值,本身就是同一个对象,异常的核心是存入数组的元素引用逻辑:
- Ruby中数组是可变引用类型,
permute方法里初始化的set是贯穿整个递归流程的同一个数组对象,回溯过程中对set的push、pop操作,都是直接修改这个内存地址上存储的内容。 - 执行
answer.push(set)时,仅将set对象的内存引用存入结果数组,并未拷贝一份当前时刻的序列快照。后续回溯逻辑修改set内容时,结果数组里所有指向这处内存的元素,读出来的内容都会同步变化,最终表现为“之前存入的旧值全部被替换为最新生成的序列”。
结合调试输出的流程对应:第一次递归到叶子节点时,set内容为[1,2,3],这处内存地址被存入answer;等回溯到上一层,执行set.pop移除末尾的3,再push新元素将set修改为[1,3,2]时,answer里第一个元素因为同样指向这处内存,读出来的内容自然同步变成[1,3,2],和刚push进去的第二个引用值完全一致。
修复方案
核心原则:存入结果数组的必须是当前序列的独立拷贝,不能直接保存原set的引用。
仅需调整存入逻辑,将拷贝后的快照放入结果数组即可,当前场景下set是一维数组,浅拷贝完全满足需求:
def find_perm(nums, answer, set) if nums.empty? p set answer.push(set.dup) # 关键修改:拷贝当前set的值生成独立快照再存入 p answer.object_id p answer return true end for i in (0..nums.length - 1) do new_nums = nums.clone new_nums.delete_at(i) set.push(nums[i]) find_perm(new_nums, answer, set) set.pop end end def permute(nums) answer = [] set = [] find_perm(nums, answer, set) answer # 原代码误将递归返回的布尔值作为结果返回,此处修正为返回实际收集到的排列数组 end permute([1,2,3])
修改完成后,每次存入answer的都是独立的数组实例,后续回溯过程对set的修改不会影响已经存入结果的内容,最终就能正常收集到全量排列结果。
内容的提问来源于stack exchange,提问作者Vivak kumar
相关产品推荐
相关产品推荐

