Randomizza i numeri in Lua senza ripetizioni

Question

Sto facendo un progetto in Lua che comporta la randomizzazione di numeri senza ripetizioni. Ecco il mio codice

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 

Fondamentalmente si mette un valore al rndom [num] in modo che quando il numero randomizzato ripete e rndom [num] ~ = nil, sarà casuale nuovo numero. Il mio problema è che ci vuole troppo tempo per caricarsi mentre la mia 'i' diventa più alta e arriverà un tempo in cui si fermerà. Immagino sia perché il randomizzatore non può ottenere un rndom [num] che è 'nil'. Voglio dire, quali sono le probabilità giusto? Mi piacerebbe migliorare il tempo di esecuzione. Chiunque può suggerire una soluzione migliore al mio problema?

Grazie!

Answer 1

È preferibile generare una permutazione con complessità temporale 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 

Answer 2

Una soluzione semplice è invece di utilizzare random di nuovo quando ottieni una variabile che hai già, cercando di restituire quella successiva disponibile. In questo modo è garantito il tempo di esecuzione O(N^2) (massimo).