Lua递归实现Heap排列算法 存储排列结果全重复问题排查

Lua中表（table）是引用类型，赋值、传参、存入其他表时传递的都是同一块内存的引用，不会自动复制表内容。
你的代码里整个递归流程始终在原地修改传入的同一个表a，每次满足k==1时往perm里存的都是这个a的引用，没有保存当时a的内容快照。
递归过程中你在k==1分支当场打印a时，后续的交换操作还没执行，所以调试输出能看到正确的排列；但等全部递归跑完，a经过多轮交换已经回到初始状态{1,2,3}，perm里存的6个引用全部指向这同一个表，打印出来自然全是{1,2,3}。

往perm存储排列时，先对当前的a做一次浅拷贝，把副本存入perm即可（表内元素都是数字，浅拷贝完全满足需求）。
将原来的perm[#perm + 1] = a替换为拷贝逻辑：

-- 生成当前a的副本
local temp = {}
for i = 1, #a do
  temp[i] = a[i]
end
perm[#perm + 1] = temp

function generateperm (k,a)
  if k == 1 then
    -- 存储当前排列的副本，而非原表引用
    local cur = {}
    for i = 1, #a do
      cur[i] = a[i]
    end
    perm[#perm + 1] = cur
    io.write(table.unpack(cur))
    io.write("\n")
  else
    for i=1,k do
      generateperm(k-1,a)
      if k % 2 == 0 then
        a[i],a[k] = a[k],a[i]
      else
        a[1],a[k] = a[k],a[1]
      end
    end
  end
end

perm = {}
generateperm(3,{1,2,3})

print("==== 最终存储结果 ====")
for _, p in ipairs(perm) do
  io.write(table.unpack(p))
  io.write("\n")
end

运行后最终存储的6个排列和调试输出完全一致，为1-3的全部全排列。

注：原代码最后遍历打印的循环中，内外层迭代都使用了k,v作为变量名，内层变量会覆盖外层，属于易引发bug的写法，修复版中已调整迭代变量名避免冲突。

内容的提问来源于stack exchange，提问作者hmpf