3 ways:
paap15’s method
(which is picking random numbers until you have one that isn’t one of the numbers.)
This works fantastic if you have up to 100 or so NPCs, or even just 3-4.
The worst case of that one is when math.random keeps picking used numbers 10000 or so times in a row, which is unlikely, but a looming threat.
Deck of cards method
Make a table/array. Fill it with all 9999 possible numbers. Shuffle the array (Fisher-Yates shuffle). Start picking numbers from the start.
This is like picking cards from a shuffled deck and setting used ones aside. Because the used cards are gone, they cannot be picked again. Blindly using math.random is like picking a random card from a deck and putting the card back in the deck, so it can be chosen again.
local numbers = {}
local which = 0
local max = 9999
-- fill it up!
for i = 1, max do table.insert(numbers, i) end
-- shuffle it!
-- https://gist.github.com/Uradamus/10323382#gistcomment-2754684
for i = #numbers, 2, -1 do
local j = math.random(i)
numbers[i], numbers[j] = numbers[j], numbers[i]
end
function getNPCNumber()
assert(which < max, "NPC number limit reached")
which = which + 1
return numbers[which]
end
@Sleitnick thank you for being visible on google search!
This is guaranteed to give you a number and will not become slower and slower as it becomes more likely to pick a number that’s already in use. But it takes a lot of memory even if you only use 10 of the numbers.
Use this if you really do plan to have thousands of NPC names used, and never just 3 or 10.
(You need to modify this in a non-obvious way if you want 1, 6, 777, 3434 etc. to be the first ones to appear.)
I have no name for this. Skipping?
Make a table (list/array) for numbers that have been chosen. Pick a random number from 1 to (9999 - amount of items in table). Add 1 to the random number for each number in the array that is less than or equal to the random number. Insert the random number into the array such that the array stays sorted.
In essence, this picks one of the 9999 - n numbers that haven’t been picked, then makes it so the numbers that have been picked before, they don’t exist, just skip over them.
Example code (completely untested):
local used = {1, 6, 777, 3434} -- must be sorted ascending
local max = 9999
function getNPCNumber()
assert(#used < max, "NPC number limit reached")
local number = math.random(1, max - #used)
for i,v in ipairs(used) do
if v <= number then
-- skip this number
number = number + 1
else
-- pick this number, and add it to the list of used numbers
-- before the number that was just checked, which is
-- greater than the random number which is greater than
-- the previously checked number
table.insert(used, i, number)
return number
end
end
-- the random number is the highest one yet (or there are none in there at all)
table.insert(used, number)
return number
end
I won’t bother to check whether the statistics of this check out, but I think it’d work.
Similarly to 1, it only uses as much memory as you have names, but similarly to 2, it is guaranteed to return within 9999 iterations; this worst case only happens once or twice when all numbers 1-9950 have been picked and it has to go through the 9950 first numbers to check the latter ones.
You can use a binary search to make searching the table take no time as well, but it’s fine as-is.
