random number without duplicate [SOLVED]

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
test
Prole
Posts: 28
Joined: Sun Apr 14, 2019 2:36 pm

random number without duplicate [SOLVED]

Post by test » Tue May 07, 2019 7:04 pm

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.
Last edited by test on Wed May 08, 2019 11:02 am, edited 1 time in total.

Nelvin
Citizen
Posts: 98
Joined: Mon Sep 12, 2016 7:52 am
Location: Germany

Re: random number without duplicate

Post by Nelvin » 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

milon
Citizen
Posts: 60
Joined: Thu Jan 18, 2018 9:14 pm

Re: random number without duplicate

Post by milon » Tue May 07, 2019 8:13 pm

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
Party member
Posts: 595
Joined: Sat Jul 22, 2017 7:43 pm

Re: random number without duplicate

Post by grump » Tue May 07, 2019 8:48 pm

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.

User avatar
pgimeno
Party member
Posts: 1943
Joined: Sun Oct 18, 2015 2:58 pm
Location: Valencia, ES

Re: random number without duplicate

Post by pgimeno » Tue May 07, 2019 11:02 pm

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

Nelvin
Citizen
Posts: 98
Joined: Mon Sep 12, 2016 7:52 am
Location: Germany

Re: random number without duplicate

Post by Nelvin » Tue May 07, 2019 11:16 pm

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.

User avatar
pgimeno
Party member
Posts: 1943
Joined: Sun Oct 18, 2015 2:58 pm
Location: Valencia, ES

Re: random number without duplicate

Post by pgimeno » Tue May 07, 2019 11:25 pm

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

Post Reply

Who is online

Users browsing this forum: No registered users and 4 guests