Scripting Helpers is winding down operations and is now read-only. More info→
Ad
Log in to vote
-1

How can I form a random number sequence?

Asked by
Zerio920 285 Moderation Voter
9 years ago

So say I wanted to randomly order numbers from 1 through 10. I could always do

math.random(1,10)

10 times. But I think if I did that, I might get some numbers that are the same. I mean like, for one instance it might pick 5, the next instance it might pick 8, and the next instance it might pick 5 again. I want the numbers to all be different, so each number only gets picked once, if you get what I mean.

So for example say math.random(1,10) chose 3. So the next math.random would have to pick numbers between 1-10, but not 3. How would I do this?

1 answer

Log in to vote
2
Answered by
BlueTaslem 18071 Moderation Voter Administrator Community Moderator Super Administrator
9 years ago

There's a number of different ways to do this.

The most straightforward would be to shuffle:

local list = {};
for i = 1, 10 do
    list[i] = i;
end
-- `list` is filled with the numbers 1 to 10

Fisher-Yates / Knuth (Fair) Shuffle

I'm not sure how to justify why the Fisher-Yates shuffle is a fair-shuffle (doesn't bias towards particular permutations at all) however it is the standard one. It looks like this:

for i = 1, #list do
    local j = math.random(i, #list);
    list[i], list[j] = list[j], list[i];
end

list is then shuffle randomly.


I'll edit my post and provide three more approaches (but this is the one you should probably go with)



"Removing" Shuffle

Here's a sort of different way to shuffle. Rather than being "in-place", it makes a new list out of the old one. Instead of doing swaps, we just pick one at random and take that out of the running:

-- using same `list` filled with 1 to 10
local shuffled = {}
while #list > 0 do
    table.insert( shuffled,
        table.remove(list, math.random(1,#list) )
    );
end

I suppose we could do the above in-place with a little modification; it becomes very similar to the Fisher-Yates shuffle.

In-Place "Removing" Shuffle

-- same `list`
local un = #list;
while un > 0 do
    table.insert(list,
        table.remove(list,math.random(1,un) )
    )
    un = un - 1;
end


Non-Deterministic Guessing Shuffle

Here's a simple way that is a bad idea, but will work. Instead of actually guaranteeing we pick unique elements for each position, we just keep picking a value until it is one that we haven't picked. (Also not in-place)

out = {}
-- same `list`
local num = #list;
for i = 1, num do
    local r;
    repeat
        r = math.random(1,num)
    until list[r]
    out[i], list[r] = list[r], nil;
end

This is bad since it could repeatedly waste time picking elements that are wrong and having to try again. This would be very slow if we consider having a list of 1000 elements -- the last guess would be wrong 99.9% of the time, so we'd expect it to do 692 guesses just to get the last element, even though there's only one valid choice.

All the previous algorithms are linear time in the size of list (double the size, double the time) while this one is roughly quadratic (double the size, quadruple the time required)



Random Sorting

Here's an interesting way to do it. It's linearithmic instead of linear. (Linearithmic means n * log(n); double the size and you slightly more than double the time required)

We assign make our list of ten elements, but instead we pair it with a random number. We then sort by that random number and then extra our list from it:

list = {}
for i = 1, 10 do
    list[i] = {i, math.random() }
end

table.sort(list, function(a,b) return a[2] < b[2] end );
-- Sort by second element

for i = 1, #list do
    list[i] = list[i][1]
    -- Remove the random number since it's not relevant anymore
end
Ad

Answer this question