Shuffling a Table

Resources Community Tutorials
,
1

Hello Developer Forum community,

I just wanted to share this method with you all for shuffling an array. The way you can shuffle it is using the less-known Random.new():Shuffle(table) method. I was going to go write a shuffling algorithm manually, but found this gold instead!

Here are the docs for this.

Have a great day everybody!

7 Likes
2

Oh that’s actually interesting, never seen that method before.

Genuinely curious, table.sort with Random.new() would work for shuffling as well right?

1 Like
3

I could be mistaken, as I am not too experienced in this all, but if you used table.sort in this fashion:

local function shuffle(t)
    local rng = Random.new()
    table.sort(t, function(a, b)
        return rng:NextNumber() < 0.5
    end)
end

The result would be a potentially biased shuffle in that table.sort assumes a consistent comparator—like when you use it to sort by greater value or something. If you feed it random numbers like rng in our example here, some orders might be more likely than others depending on the sorting algorithm’s internal structure.

The alternative then would be the Fisher-Yates shuffle, which should give you uniform distribution. Instead of manually programming that (which you can still do if you like using table.sort and Random.new():NextInteger()), it appears we can just use Random’s :Shuffle() for sake of convenience.

Here’s what it would look like if you wanted to sort it using Fisher-Yates manually:

local function shuffle(t)
    local rng = Random.new()
    for i = #t, 2, -1 do
        local j = rng:NextInteger(1, i)
        t[i], t[j] = t[j], t[i]
    end
end

Let me know what you think, this is a fascinating topic I love it!

1 Like
4

yes but why?

local rand = function():boolean

return math.random()>0.5
end
table.sort(tableHere,rand)

plus this would most likely be less performant than method from Random.new

2 Likes
5

Oh I was just asking to ask lol, because if that method never existed I’d be using table.sort. Method is cool though.

6

Helpful resource for bros with manual implementations of the Fisher-Yates shuffle (I am bros, and I do not know how I did not know about this)

I was going to go write a shuffling algorithm manually, but found this gold instead!

Thanks for sharing this gold

1 Like
7

I’m glad to know it helped! It’s definitely a fun topic to play with :face_with_tongue:

8

who tf came up with this and not table.shuffle instead??

3 Likes
9

No. Well yes but the output will be very much biased.

image
image1168Ă—677 38.3 KB

Fisher-Yates is a rather simple algorithm with a much higher quality output.
image
image1174Ă—667 30.2 KB

Sample implementation in Luau:

local function FisherYates(tbl)
  for i = #tbl, 1, -1 do
    local j = math.random(1, i)
    tbl[i], tbl[j] = tbl[j], tbl[i] 
  end
end
3 Likes
10

I want to make a quick point: Fisher-yates is the proper way to perform an array shuffle (which is what rng:Shuffle uses according to the docs).

Simply sorting with random numbers doesn’t work because the table.sort algorithm relies on stable values per key. You’ll get in error: invalid order function for sorting.

2 Likes
11

In most cases at least

1 Like
12

Ahhhh, yeah that makes a lot of sense. The method with table.sort() is very likely to produce similar patterns with every iteration, hence why it’s not really a uniform distribution.

Will keep in mind.

2 Likes