Page 1 of 1

random number without duplicate [SOLVED]

Posted: Tue May 07, 2019 7:04 pm
by test

Code: Select all

local x = love.math.random(1, 4)
local y = love.math.random(1, 4) -- y ~= x
I want x to be different than y. For example 2 and 3 but not 3 and 3.

Re: random number without duplicate

Posted: Tue May 07, 2019 8:09 pm
by Nelvin
Most simple/pragmatic solution

Code: Select all

local x = love.math.random(1, 4)
local y = love.math.random(1, 3)
if x == y then y = y + 1 end

Re: random number without duplicate

Posted: Tue May 07, 2019 8:13 pm
by milon
Another option:

Code: Select all

local x, y
x = love.math.random(1, 4)
repeat
    y = love.math.random(1, 4)
until x ~= y
Both mine & Nelvin's should be indistinguishable to users.

Re: random number without duplicate

Posted: Tue May 07, 2019 8:48 pm
by grump
An actually working and simple solution is to create a list of all possible values, select one randomly, then delete the selected entry from the list of possible values.

A more sophistacted approach is a Feistel network, more practical information here.

Re: random number without duplicate

Posted: Tue May 07, 2019 11:02 pm
by pgimeno
A Feistel network is only applicable to powers of two; otherwise you need to discard numbers. Then there's the problem of seeding.

The list method is more general, as it allows for N different elements instead of just two or powers of two. And as an improvement, rather than deleting elements, you can swap them out, which is O(1) instead of O(N). Applied to this case:

Code: Select all

local list = {1, 2, 3, 4}
local N = #list
local numbers_to_extract = 2

for i = 1, numbers_to_extract do
    local rand = math.random(i, N)
    list[i], list[rand] = list[rand], list[i]
end
The first numbers_to_extract elements in list[] will have the random elements; in this case, list[1] and list[2].

That's also the underlying method behind Fisher-Yates shuffle, except in Fisher-Yates, numbers_to_extract equals N-1.

Edit:
Nelvin wrote: Tue May 07, 2019 8:09 pm Most simple/pragmatic solution

Code: Select all

local x = love.math.random(1, 4)
local y = love.math.random(1, 3)
if x == y then y = y + 1 end
This isn't uniform. You will only get a 4 in the second number if the first one is a 3, so the pairs (1, 4) and (2, 4) don't appear at all. I think you meant <= instead of ==.

Re: random number without duplicate

Posted: Tue May 07, 2019 11:16 pm
by Nelvin
pgimeno wrote: Tue May 07, 2019 11:02 pm
Nelvin wrote: Tue May 07, 2019 8:09 pm Most simple/pragmatic solution

Code: Select all

local x = love.math.random(1, 4)
local y = love.math.random(1, 3)
if x == y then y = y + 1 end
This isn't uniform. You will only get a 4 in the second number if the first one is a 3, so the pairs (1, 4) and (2, 4) don't appear at all.
Good catch, haven't really thought about it - but it's also a question of the actual range of values used. If it's about a random position on a fullHD display, it doesn't matter, but for lower ranges, my suggestion was/is pure crap.

Re: random number without duplicate

Posted: Tue May 07, 2019 11:25 pm
by pgimeno
(@Nelvin - Don't miss my last edit)