How to make a function that never pick twice the same number in Lua

Question

I'm trying to make a function that generate random number, but never twice.

Here is what I got so far, but it doesn't work. It compiles, but then again it insert multiple times the same number in my array.

quiz = 10
array = {}
array[1] = 0 -- just to have something in it because it won't work in my loop otherwise...
ok = false

repeat
    rdm = math.ceil(math.random() * quiz)

    for i = 0, #array do
        if(rdm == array[i]) then
            break -- to break the for loop to pick a new number
        elseif(rdm ~= array[i]) then
            ok = true -- to end the repeat loop
            table.insert(array, rdm) -- to keep a track of what I got so far
        end
    end
until ok == true

for b = 0, #array do -- #array should be ten
    print(array[b])
end

What it does is it generate multiple times the same number and says it's different from the one in the table...

I guess my problem comes from logic... but I don't know where cause it all make sense for me

Answer 1

If you know you are going to need at most N numbers, you could pregenerate the random numbers and insert them in a table according to their value. Then your function randomly picks a number from that table and removes the number. Something like:

local rands = {}
local numRands = 100

-- populate table of random numbers
while #rands < numRands do
    local r = math.random(1,1000)
    rands[r]=r -- if duplicate, table stays same
end

local function getNeverSameRandom() 
    local index = math.random(1,numRands)
    return table.remove(rands, index)
end

If you don't know how many to populate, then keep track via table:

local randsUsed = {}
local maxRand = 1000000 -- largest random # you want
local function getNeverSameRandom() 
    local rnd
    repeat 
         rnd = math.random(1,maxRand)
    until randsUsed[rnd] == nil
    randsUsed[rnd] = rnd
    return rnd
end

The problem of course is that if you call getNeverSameRandom many times, like half the max random number, your randsUsed table is going to get quite full, and the repeat-until is going to take longer and longer. Eventually, the table will be full, and the function will be in an infinite loop. You could easily check by keeping track with a counter, but you cannot use #randsUsed because randsUsed is a table with "holes" so the # operation can't be used. For example:

local randsUsedCount  = 0
local function getNeverSameRandom() 
    if randsUsedCount == maxRand then
        error("No more random #'s left in range 1-"..maxRand)
    end
    local rnd
    repeat 
         rnd = math.random(1,maxRand)
    until randsUsed[rnd] == nil
    randsUsed[rnd] = rnd
    randsUsedCount = randsUsedCount  + 1
    return rnd
end

Answer 2

The simplest way is to probably prepopulate an array of elements with the sequence you need (for example, 1..1000) and then shuffle the elements in place using something like Fisher-Yates algorithm:

local rands, n = {}, 1000
-- prepopulate
for i = 1, n do rands[i] = i end
-- shuffle
for i = n, 2, -1 do
  local j = math.random(i)
  rands[j], rands[i] = rands[i], rands[j]
end
-- use
print(table.remove(rands))

The same page also has "inside-out" version of the algorithm that does both initialization and shuffling.