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?
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
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)
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.
-- same `list` local un = #list; while un > 0 do table.insert(list, table.remove(list,math.random(1,un) ) ) un = un - 1; end
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)
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