You need to enable JavaScript to run this app. Ruby backtracking中数组传参不当导致全排列结果异常
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.04 15:06:03