Scripting HelpersARCHIVE
A little piece of Roblox history. Preserved for everyone, one question at a time.Read about the archive →
✓ ANSWER ACCEPTED

How can I form a random number sequence?

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

✓ Accepted answer

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

This discussion is preserved as it was. New answers, comments, and votes are closed.