Nonrepeating random numbers?

[Dreken]

Hey guys, I'm trying to make a spawn system for my entities that spawns them at 30 random locations, and 15 of them are active at any one time.

So far, the re spawn system works, but I have to set a position for them. If I do math.random(0,30) calling my table of 30 locations, obviously some are going to stack on top of one another, because the same random number can occur twice.

Is there any way to generate non repeating random numbers so 15 of these entities spawn in 15 unique locations from a pool of 30 locations?

[Ott]

-snip-

[Turbine]

You could use an array or bitwise number of already placed locations. So if it decides to pick one which it's already chosen, it could keep trying until it's there.

Or even better have an array of all the locations and remove them as they're used, making the random only select from a list of unused locations.

[Whiterabbit]

Have an array with all the numbers you need (1-30).
Shuffle that array [url]http://www.gammon.com.au/forum/?id=9908[/url]
Then you can just use the first 15 entries.

I just realised this is what turbine is saying. I concur.
[quote]Or even better have an array of all the locations and remove them as they're used, making the random only select from a list of unused locations. [/quote]

[Ludicium]

This might do the trick.

[lua]
local function getRandomIndexes( numberToReturn, tbl )
local out_locs = {}
local try = 0
local try_limit = 50000

while (#out_locs < numberToReturn) do
local rand_loc = table.Random(tbl)
if (not table.HasValue(out_locs, rand_loc)) then
table.insert(out_locs, rand_loc)
end
if (try >= try_limit) then
break
end
end

return out_locs
end
[/lua]

I think this might be a better method.

[lua]
local function getRandomIndexes( numberToReturn, tbl )
local out_tbl = {}
for k,v in RandomPairs(tbl) do
table.insert(out_table, v)
if (#out_table == numberToReturn) then
return out_table
end
end
return out_table
end
[/lua]

[Whiterabbit]

[QUOTE=Ludicium;40553887]
I think this might be a better method.

[lua]
local function getRandomIndexes( numberToReturn, tbl )
local out_tbl = {}
for k,v in RandomPairs(tbl) do
table.insert(out_table, v)
if (#out_table == numberToReturn) then
return out_table
end
end
return out_table
end
[/lua][/QUOTE]

Nice, I wasn't aware of the RandomPairs function.

[Kogitsune]

function PickRandom( unused, used )
  if #unused == 0 then
    while #used > 0 do
      table.insert( unused, table.remove( used, math.random( #used ) ) )
    end
  end

  local a = table.remove( unused, math.random( #unused ) )
  table.insert( used, a )

  return a
end

Or something like that. Uses two tables to track used/unused items and will shuffle the used points back in when it runs out of unused ones - not tested.

[Ludicium]

[QUOTE=Kogitsune;40554179]

function PickRandom( unused, used )
  if #unused == 0 then
    while #used > 0 do
      table.insert( unused, table.remove( used, math.random( #used ) ) )
    end
  end

  local a = table.remove( unused, math.random( #unused ) )
  table.insert( used, a )

  return a
end

Or something like that. Uses two tables to track used/unused items and will shuffle the used points back in when it runs out of unused ones - not tested.[/QUOTE]

I like that but, I think it would be more suited if it was 1 table with two dimensions, simply for condensing sake. Ex table.used & table.unused. Not a big change but now you only have to handle one variable in and out of the function.

[Kogitsune]

[QUOTE=Ludicium;40561249]I like that but, I think it would be more suited if it was 1 table with two dimensions, simply for condensing sake. Ex table.used & table.unused. Not a big change but now you only have to handle one variable in and out of the function.[/QUOTE]

Like I said, it is just an example of how I would approach it. There's multiple ways to go about it and they each have their own advantages.

[thegrb93]

Simplest method here
[lua]
local tbl = {}
for i = 1, 30 do
tbl[i] = i
end
for i = 1, 15 do
local rand = tbl.remove(math.random(#tbl))

--your code here
end
[/lua]

[Ghor]

Removing entries from anywhere but the end of the table is relatively expensive, and it's not necessary. Generate a table (t) with numbers from min to max of your random range, shuffle the table, then keep an index counter (i). On each call to the function, read t[i] and increment i. When i > #t, reshuffle t and reset i back to 1.

[lua]
-- Shuffles a numerically-indexed table. Not 100% sure it's the best implementation, but it should suffice.
local function ShuffleTable( t )
local size = #t
for i=1,size do
local randomIndex = math.random(1,size)
t[i],t[randomIndex] = t[randomIndex],t[i]
end
end

-- Generates and returns a new function for getting nonrepeating random numbers, from "min" to "max".
function CreateRNG( min, max )
-- Make sure "min" isn't greater than "max".
if ( min > max ) then
min, max = max, min
end

-- Store how many elements are between "min" and "max". We will be using this often.
local size = (max-min)+1

-- Generate our table of possible results.
local t = {}
for i=1,size do
t[i] = min+(i-1)
end

-- Keep an index counter. This counter is incremented on each call to the new function, and is used to select a value from the number table. If it becomes greater than "size", we reset it to 1 and shuffle the table.
local index = size -- Force the table to shuffle for the first time when the function is first called.

-- Generate and return the function. This has negligible overhead, thanks to Lua's function closure mechanic.
return function()
index = index+1
-- Reset the index counter if it's out-of-range. You can add special-case handling here for the event that t[#t] becomes t[1] after the shuffle, which would give you the same number twice.
if ( index > size ) then
index = 1
ShuffleTable( t )
end
return t[index]
end
end

-- Some example usage code:
local RandomFrom10To25 = CreateRNG( 10, 25 )
print( RandomFrom10To25() )
print( RandomFrom10To25() )
print( RandomFrom10To25() )
[/lua]

If necessary, you can easily modify this to return arbitrary values by filling a table with your pool of results and supplying it as "t".

[thegrb93]

table.remove isn't expensive so long as the table is small.

[FPtje]

[QUOTE=thegrb93;40575729]table.remove isn't expensive so long as the table is small.[/QUOTE]

You're making an assumption about the input size, which you shouldn't do. Table.remove takes O(n) time. An algorithm selecting m numbers would take O(n *m) time which is something you don't want.

The random pairs might be expensive because you don't know how expensive it is, but I'm guessing it's O(n).

This can be done in O(m) time without using table.remove and without the use of extra tables (besides the result table of course) . I'll show you when I'm on my laptop.

Edit:

[lua]function getRandomEntries(tbl, amount)
local result = {}
local top = #tbl

-- Loop invariant: tbl[1 .. top] contains values that are NOT in result
while #result < amount and top > 0 do
local rand = math.random(1, top)
local val = tbl[rand]

table.insert(result, val)
tbl[rand] = tbl[top] -- simply switch with values that you're not going to look at anymore
tbl[top] = val

top = top - 1
end

return result
end[/lua]
- the running time is fixed and low, if you want m numbers, it will iterate m times. Regardless of how big the table is.
- it leaves the table mostly intact, it only messes with the order. This means the same table can be re-used (assuming the order of the values doesn't matter, as mentioned in OP)
- if amount >= #tbl it will just return a random permutation of the table

[editline]9th May 2013[/editline]

[QUOTE=Turbine;40553237]You could use an array or bitwise number of already placed locations. So if it decides to pick one which it's already chosen, it could keep trying until it's there.
[/QUOTE]
The running time of this algorithm could theoretically be infinite. In practice you'll find that such algorithm can sometimes take much longer than other times. The practical running time of this algorithm will increase dramatically as the amount of values you want to take from the table gets close to the amount of values the table has in total.

Let me show you with an example:

Say you have 30 things in your table, and you want 29 unique random things in it. You use math.random(1, 30) to take random values until you have 29 unique values. You throw away duplicate values.
When you have 28 numbers, you only need ONE more. Two of the table are still available, but the math.random looks at the numbers from 1 to 30 at random. The chance is 1 in 15 that you'll get your value each iteration, which makes the expected running time 15 iterations. 15 iterations [b]just[/b] to get the last value!

[editline]9th May 2013[/editline]

Ghor's algorithm is too expensive.
Give Ghor a table with a million values, asking three unique indices.
Ghor will do at least a million steps to first create a table of possible indices and then another million to shuffle the table of indices. This makes his algorithm O(n) time in the size of the table (max - min in his case)

[Ludicium]

[QUOTE]O(n)[/QUOTE]

Big O notation is not something I expected to ever see on Facepunch. Are you a CS, CE, or SE major?

[FPtje]

Computer Science second year. :D How about you?

[Ghor]

[QUOTE=FPtje;40579409]
Ghor's algorithm is too expensive.
Give Ghor a table with a million values, asking three unique indices.
Ghor will do at least a million steps to first create a table of possible indices and then another million to shuffle the table of indices. This makes his algorithm O(n) time in the size of the table (max - min in his case)[/QUOTE]

This isn't a function for working with a million values and asking three unique indices. This is a one-time call for generating the RNG function "f()" you will be calling for all future selections of random values in the given set. t is generated in-function for the sake of usage simplicity. If you want to have a table of non-numeric values or non-contiguous numbers as possible results for f(), you should be removing the t generation and supplying your own as an argument. As it is, if the table contains n values f() is only performing an n-based operation after every n calls. If all I changed in f() was the execution of a single value swap on each call ( t[i], t[math.random(i,#t)] ) instead of shuffling the whole table upon overflow, the call to select a random value should be O(1), but the average time to make n calls remains the same.

[&gt;&gt;oubliet]

[QUOTE=FPtje;40579409]-stuff-[/QUOTE]

Switching used values with the top value will cause the top value to have considerably more chance than any other value, it's safer to just tbl[ key ] = nil it.

[FPtje]

[QUOTE=>>oubliette<<;40582511]Switching used values with the top value will cause the top value to have considerably more chance than any other value[/QUOTE]
No, because the top is different every time. The top decreases with each iteration. It has the same chance as any other value that hasn't been put in result yet
[img_thumb]http://www.imgur.com/5vVyTHM.png[/img_thumb]

[editline]9th May 2013[/editline]

[QUOTE=Ghor;40582344]This isn't a function for working with a million values and asking three unique indices. [/QUOTE]
The extreme shows my point. The amount of redundant work you're doing scales with n - m. You're defining your function for a dynamic input size. It wouldn't be a parameter if it wasn't.
Your given algorithm iterates over the entire table of size n to give m values. If the table contains 3 values, and the user wants 2 unique random values from it, you do 2 * 1 iteration too many. If the table contains a 30 values, and the user wants 3, your algorithm does 10 * 2 - 3 too many iterations

[QUOTE=Ghor;40582344]This is a one-time call for generating the RNG function "f()" you will be calling for all future selections of random values in the given set.[/quote]
Which is O(n)

[QUOTE=Ghor;40582344]If all I changed in f() was the execution of a single value swap on each call ( t[i], t[math.random(i,#t)] ) instead of shuffling the whole table upon overflow, the call to select a random value should be O(1)[/QUOTE]
That could be one way of getting rid of the O(n).

[QUOTE=Ghor;40582344]but the [b]average[/b] time to make n calls is the same.[/QUOTE]
[url=http://en.wikipedia.org/wiki/Amortized_analysis]Amortized*[/url]. The amortized speed of your algorithm is O(1) if you take n numbers, but you're not taking n numbers, but m (with m < n). Besides, the amortized speeds aren't really interesting here. What's interesting here is that you're doing O(n) work at the beginning. I know that most calls of f() after you've done RNG() are O(1), but you're doing O(n) work to get there in the first place.

[editline]9th May 2013[/editline]

I love these discussions.

[Ghor]

[QUOTE=FPtje;40582693]
The extreme shows my point. The amount of redundant work you're doing scales with n - m. You're defining your function for a dynamic input size. It wouldn't be a parameter if it wasn't.
Your given algorithm iterates over the entire table of size n to give m values. If the table contains 3 values, and the user wants 2 unique random values from it, you do 2 * 1 iteration too many. If the table contains a 30 values, and the user wants 3, your algorithm does 10 * 2 - 3 too many iterations

...

[url=http://en.wikipedia.org/wiki/Amortized_analysis]Amortized*[/url]. The amortized speed of your algorithm is O(1) if you take n numbers, but you're not taking n numbers, but m (with m < n). Besides, the amortized speeds aren't really interesting here. What's interesting here is that you're doing O(n) work at the beginning. I know that most calls of f() after you've done RNG() are O(1), but you're doing O(n) work to get there in the first place.[/QUOTE]

For the needs of the topic's creator, the selection of 15/30 entity spawn locations, the number of calls to f() is anticipated to be several times the value of n; RNG() is called once at load time and the returned function f() is called for all selections until the Lua state is destroyed when the server shuts down, and over the lifetime of the Lua state several entity spawn cycles will occur. Be mindful that you are also comparing our solutions in unequal scope. You are not accounting for the generation of the data set used by your method, yet you include it in mine.

[FPtje]

[QUOTE=Ghor;40583051]For the needs of the topic's creator, the selection of 15/30 entity spawn locations, the number of calls to f() is anticipated to be several times the value of n;[/QUOTE]
Oh, right, I assumed m <= n because you can only take n unique random values from a table. I didn't think you had reusing in mind.

[QUOTE=Ghor;40583051]RNG() is called once at load time and the returned function f() is called for all selections until the Lua state is destroyed when the server shuts down, and over the lifetime of the Lua state several entity spawn cycles will occur. [/quote]
Also, doesn't this have side effects? (this is something different, but I feel it needs mentioning)
Say OP wants 15 random spawns, he calls f() 15 times. Then in a different situation (a new round or something) he calls f() another 15 times. With the 30 spawns that he has, the first 15 are always different than the last 15. This is probably not [i]really[/i] a bad thing, since they're random anyway, but you're limiting the possibilities for each batch of 15 spawns.

With 30 spawns, the next 15 spawn points can be predicted based on the 15 spawn points of the last round.

[QUOTE=Ghor;40583051]You are not accounting for the generation of the data set used by your method, yet you include it in mine.[/QUOTE]
That's because my method doesn't generate any data besides the direct result. You give one number at a time, I give them all at once. The difference is that your algorithm does O(n) work at the beginning, and mine doesn't do O(n) work at all (unless m >= n). But your algorithm would be as good as mine (in speed) if you don't do O(n) work and replace the shuffle with the swapping, as you mentioned.

[editline]9th May 2013[/editline]

Speaking of using f() more often than n, I don't think your solution gives unique values if the table overflows during a batch of calls to f()
Assume n = 40, three batches of 15 spawn positions are retrieved with f().
In the third batch, the index will go from 30-40 and 1-5. In your given code it reshuffles the table. This means a value that was at, say, t[35] could go to t[3] after the overflow, only then to be retrieved twice. I think you have a similar problem if you apply the swapping.

Your algorithm can give duplicates with a chance, because your f() doesn't know how many unique values the caller wants. This is a [url=http://en.wikipedia.org/wiki/Monte_Carlo_algorithm]Monte Carlo[/url] algorithm by the book!

[Ghor]

[QUOTE=FPtje;40583363]Oh, right, I assumed m <= n because you can only take n unique random values from a table. I didn't think you had reusing in mind.

Also, doesn't this have side effects? (this is something different, but I feel it needs mentioning)
Say OP wants 15 random spawns, he calls f() 15 times. Then in a different situation (a new round or something) he calls f() another 15 times. With the 30 spawns that he has, the first 15 are always different than the last 15. This is probably not [i]really[/i] a bad thing, since they're random anyway, but you're limiting the possibilities for each batch of 15 spawns.

With 30 spawns, the next 15 spawn points can be predicted based on the 15 spawn points of the last round.

That's because my method doesn't generate any data besides the direct result. You give one number at a time, I give them all at once. The difference is that your algorithm does O(n) work at the beginning, and mine doesn't do O(n) work at all (unless m >= n). But your algorithm would be as good as mine (in speed) if you don't do O(n) work and replace the shuffle with the swapping, as you mentioned.[/QUOTE]

[lua]

-- Generates a table containing the set of numbers between "min" and "max" in ascending order.
local function GetNumbersInRange( min, max )
-- Make sure "min" isn't greater than "max".
if ( min > max ) then
min, max = max, min
end
local t = {}
for i=1,max-min+1 do
t[i] = min+(i-1)
end
return t
end

-- Generates and returns a new function for getting nonrepeating random elements in numerically-indexed table "t".
-- Passing true as the first argument to the new function will reset the result blacklist immediately.
function CreateRNG( t )
-- Store the size of the table, since we will be using it often. This assumes "t" will be of static length.
local size = #t

if ( size == 0 ) then
-- Throw error.
end

if ( size == 1 ) then
return function() return t[1] end
end

-- Keep an index counter. This counter is incremented on each call to the new function, and is used to select a value from the number table. If it becomes greater than "size", we reset it to 1.
local index = 0 -- The first call to the returned function will make this 1.

-- Generate and return the function. This has negligible overhead, thanks to Lua's function closure mechanic.
local function f( bReset )
index = index+1
-- Reset the index counter if it's out-of-range.
if ( ( index > size ) or bReset ) then
index = 1
-- Special-case handling here to be sure t[1] won't become t[size] after overflow, which would give you the same number twice in a row.
local randomIndex = math.random( 1, size-1 )
t[size],t[randomIndex] = t[randomIndex],t[size]
end
local randomIndex = math.random( index, size )
t[index], t[randomIndex] = t[randomIndex], t[index]
return t[index]
end
return f
end

-- Some example usage code:

-- Generate our table of possible results.
local numbersFrom10To25 = GetNumbersInRange( 10, 25 )

-- Create an RNG for our table.
local RandomFrom10To25 = CreateRNG( numbersFrom10To25 )

-- Print three nonrepeating numbers from the RNG.
print( RandomFrom10To25() )
print( RandomFrom10To25() )
print( RandomFrom10To25() )
-- Print another three nonrepeating numbers from the RNG, which can overlap with the first three.
print( RandomFrom10To25( true ) )
print( RandomFrom10To25() )
print( RandomFrom10To25() )
[/lua]

Call f(true) to "forget" which values have been previously returned without waiting for the overflow.

[FPtje]

Your algorithm pretty much does the same thing as mine now :v:
You go over the table from "left" to "right", with your invariant being that for every i < index, t[i] is a taken value (until you call it with true as parameter, then it'll reset)

I go over the table from right to left, with my invariant being that for every i > top, t[i] is a taken value.
In your new example it's more clear to see that GetNumbersInRange() is not necessary for your algorithm to work. It looks like your algorithm has the same complexity as mine. Nice work.

One small thing is that the OP needs to be aware that he needs to call f(true) at the beginning of each batch of 15 spawns. It's definitely not a bad thing algorithm-wise, but it might be frowned upon by some people as an unclear design choice (easy to get wrong and hard to debug when you forget it). But that's just nitpicking.

Edit:
Actually, I think it should error when it overflows. An overflow is a risk of duplicate values, except for the first value after an overflow, you caught that in a special case (I'm not sure why). It shouldn't be allowed to overflow in the first place since that means the caller forgot to reset it.

[&gt;&gt;oubliet]

Sorry for the messy code, but this is how I'd do it :

[lua]
local table = {};

for i = 0, 500 do

table[ i ] = math.random( 1, 1000 );

end

local function randomNoRepeat( tbl, isNumeric )

local len = isNumeric and #tbl or table.Count( tbl );
local targ = math.random( 1, len );

local new, i, value = tbl, 0;

if ( tisNumeric ) then

value = tbl[ targ ];
new[ targ ] = nil;

else

for k, v in pairs( tbl ) do

if ( i == targ ) then

value = v;
new[ k ] = nil;
break;

end

i = i + 1;

end

end

return value, new;

end

local _table = table;
local function getRandom()

local len = type( #_table ) == "number" and #_table or table.Count( _table );

if ( len <= 0 ) then _table = table; end

local rand, tab = randomNoRepeat( _table, true )

_table = tab;

return rand;

end
[/lua]

This code would probably have the least predictable patterns, which is probably best for what OP wants.

[FPtje]

[lua]type( #tbl ) == "number"[/lua]
type is expensive, but why would you check whether the length of a table is a number? It always is. Even if all keys are not numeric:
[lua]a = {}
a.b = 3
a.c = 5
print(#a)
> 0
[/lua]

Also, table.Count is O(n), but since you're taking non-numeric keys in account (unlike Ghor and I), I can't blame you for that one.

[lua]local new, ... = table, ...[/lua]
Doesn't actually make a copy of the table. Use table.Copy instead.

edit;
I have to remove half of my post because you edited your algorithm ._.

Your algorithm is still wrong. When doing tbl[targ] = nil you leave a hole in the table. A next call of the function could give you a targ equal an index that was previously removed.

Edit:
[b]Conclusion so far[/b]
We got pretty deep in a discussion invoking terms like closure, monte carlo algorithm, big O notations, amortized costs and stuff like that. I think the OP wants a simple conclusion (if he hasn't found a different solution elsewhere :v:).

In my opinion, it comes down to two algorithms:
Ghor's last algorithm makes nice usage of closure. The nice thing about his algorithm is that you don't have get the batch of spawn positions all at once, you can get them one at a time when you need them.
My algorithm is simple and gives you the 15 spawn positions you need, but it gives them all at once.

Ghor's algorithm and my algorithm are equally fast, and are the fastest ones posted thus far. I recommend a choice between either:
Ghor's: [url]http://facepunch.com/showthread.php?t=1268720&p=40584115&viewfull=1#post40584115[/url]
Mine: [url]http://facepunch.com/showthread.php?t=1268720&p=40579409&viewfull=1#post40579409[/url]

Ghor's algorithm looks more complicated than it needs to be. He could trim out some base cases and long comments to make the code a lot more simple.

[Dreken]

Thanks for all your help guys. I ended up using table.remove and then doing a random number from 1 to the table length.

I don't really know the CS stuff for optimizing the code, so I stuck with that.

Coding is just a hobby XD

[FPtje]

[QUOTE=Dreken;40590525]Thanks for all your help guys. I ended up using table.remove and then doing a random number from 1 to the table length.

I don't really know the CS stuff for optimizing the code, so I stuck with that.

Coding is just a hobby XD[/QUOTE]

no no no NO! That's a really bad way of doing it!
you can copy paste my code:
[url]http://facepunch.com/showthread.php?t=1268720&p=40579409&viewfull=1#post40579409[/url]

I tested it. it works and everything. And it's REALLY easy to use!
[lua]getRandomEntries (yourTable, 15)[/lua]
The computer science stuff was to prove that it's really fast and that the other ones were really slow or didn't work. Except for Ghor's last one, which is equally fast.

the big difference between table.remove and my algorithm is that I "delete" the entries fast, and table.remove does it slowly.

[Ludicium]

[QUOTE=FPtje;40582284]Computer Science second year. :D How about you?[/QUOTE]

I am a senior in high school. I have taken AP Computer Science A, and a class in C++. This next year I will be going to school to be an computer engineer.