Randomize numbers in Lua with no repeats

Question

I am doing a project in Lua which involves randomizing numbers without repeats. Here's my code

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

Basically it puts a value to the rndom[num] so that when randomized number repeats and rndom[num] ~= nil, it will randomize number again. My problem is, it's taking too long to load as my 'i' gets higher and there will come a time that it will stop. I'm guessing it's because randomizer can't get a rndom[num] that's 'nil'. I mean, what are the odds right? I'd like to improve the running time of it. Anyone who can suggest a better solution to my problem?

Thanks!

Answer 1

It is better to generate a permutation with O(N) time complexity.

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

Answer 2

One simple solution is instead of using random again when you get a variable you already have, trying to return the next one available. That way you are guaranteed to have O(N^2) running time (maximum).