random number without duplicate [SOLVED]

[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.

[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

[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.

[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.

[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:

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 ==.

[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

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.

[pgimeno]

(@Nelvin - Don't miss my last edit)