在Lua中随机生成不重复的数字

Question

我正在使用Lua进行一个项目，其中涉及到随机生成不重复的数字。以下是我的代码：

for i = 1, 86000 do
    while rndom[num] ~= nil do
        num = math.random(1,95000)
     end
     rndom[num] = num
     for k=1, 11 do
        file2:write(input[num][k], " ")
     end
     file2:write("\n")
end

基本上，它会为rndom[num]赋值，以便当随机数字重复且rndom[num] ~= nil时，它将再次对数字进行随机化。我的问题是，随着我的“i”越来越高，加载时间太长了，并且最终会停止。我猜想这是因为随机器无法获得'nil'的rndom[num]。我的意思是，可能性有多大呢？我希望提高其运行时间。有人能建议一个更好的解决方案吗？

谢谢！

- Rachelle

Answer 1

最好使用O(N)时间复杂度生成排列。

local n = 95000

local t = {}
for i = 1, n do
   t[i] = i
end

for i = 1, 86000 do
   local j = math.random(i, n)
   t[i], t[j] = t[j], t[i]
   for k = 1, 11 do
      file2:write(input[t[i]][k], " ")
   end
   file2:write"\n"
end

- Egor Skriptunoff

---

哇，成功了！它确实使运行时间更快了。非常感谢你。 - Rachelle

Answer 2

一个简单的解决方案是，当您获取已经拥有的变量时，尝试返回下一个可用的变量，而不是再次使用random。这样可以保证最大运行时间为O(N^2)。

- Bartek Banachewicz

---

哦，你的意思是重复随机数后面的下一个数字？ - Rachelle

没错。所以，如果你随机到了5，标记一下。然后再随机一次5，看看6是否被选中。如果没有，就返回它。只要记得在达到最大值后进行包装。 - Bartek Banachewicz