LÖVE

This is just something to help you understand the Fisher-Yates shuffle, an algorithm which shuffles a table into a random order. Here is this post in an HTML page: Things in this post:

• A simple example of how you could go about shuffling a group of things.
• The exact same thing, just drawn differently, to transition into...
• Basically the exact same thing again, just with a slight difference that doesn't affect anything.
• The algorithm above written in Lua.
• An example run through.

So, let's say you have a group of things, like the shapes on the right there. And you want to put them in a random order into the area on the left.

What you could do is pick a random shape, and place it in the area on the left.
Let's say we picked the circle. Let's move it to the other side!
And now we can just repeat. Pick a random shape, and move it to the other side.
Let's pick the pentagon.
And now the square.
And, well, we don't have a choice, let's move the triangle over too.
And that's it! Shuffled.

Okay, now for the same thing, except without all the blank spaces.

Let's pick a random shape. We'll pick the same shapes as last time, so let's pick the circle.
And then, move it over to the left.
So now we pick another random shape from the area on the right. I'll put a red flag to show where the area on the right starts.
Let's pick the pentagon.
And now the square.
And hey, turns out the last shape is already there.
So, that example was the same thing as the one before. If that wasn't clear, here's both of them side by side:
Okay, now this time it'll be ever-so-slightly different. Instead shifting across the shapes on the right when one of them is placed in the area on the left, we'll swap them. You'll see.

So let's do this again, and pick a random shape, which will be the circle.



Now let's move it to the area on the left, swapping it with the triangle under the flag.
This is basically the same position we were in with the other examples after one move, except the order of the shapes in the area on the right is different. The order of the shapes on the right doesn't matter though, since we'll be picking one from there at random anyway.
Now let's pick another random shape from the area on the right, the pentagon, and swap it with whatever is under the flag, which is itself. Not a problem!
Now let's pick another random shape from the area on the right, the square, and swap it with the triangle under the flag.
And there's only one left, and it's already in the only place it can be, so we're done!
So how could we write this algorithm in English? How about...

Start with the flag at the first element.
Pick a random element between the flag and the last element.
Swap it with the element at the flag.
Move the flag along
Repeat the last three steps, stopping when the flag is at last element.

Let me conveniently rephrase that...

Loop, with the flag starting at the first element and moving along every time, and when the flag is at one-before-the-last-element this will be the final iteration, and do the following things inside the loop:
- Pick a random element between the flag and the last element
- Swap it with the element at the flag

Now here's that in Lua:
Let's see how this works with a run through!

So let's say we give this function our table of shapes...
"i" is the flag! It starts at 1, and loops through 1-less-than-the-number-of-elements times, which is 3 in this case.

Let's see what happens on the first iteration of the loop...
And the second...
And the third and final iteration...
And the table has been shuffled!

Nice explanation and beautiful images. How about putting this on the blog?

By the way, I was quiet surprised the algorithm code is so short. Only 6 lines.

Very nicely done.
One minor point that might cause confusion:
Your Lua function is correct but in your examples of its use, ‘t’ is not defined!

micha wrote:Nice explanation and beautiful images. How about putting this on the blog?
By the way, I was quiet surprised the algorithm code is so short. Only 6 lines.

Agreed.

Nice explanation. One thing though, it has a name: Fisher Yates Shuffle.

An even simpler way, using Lua's built-in table.sort.

Kyle wrote:An even simpler way, using Lua's built-in table.sort.

Code: Select all

table.sort(t, function() return math.random()>math.random() end)

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAH! That's awesome, thanks!

EDIT: Hmmm, I did a little test, and I think that might have a slight bias. Output:
Still, pretty nice for one line of code!

Inny wrote:Nice explanation. One thing though, it has a name: Fisher Yates Shuffle.

I really should have mentioned that, thanks for pointing that out! And thanks everyone for the nice words!

Interesting test. But it's not really a bias, I think. It's "truly" random, and "truly" random isn't evenly distributed. So if you wanted real, true shuffling, this method's better.

Kyle wrote:

Code: Select all

table.sort(t, function() return math.random()>math.random() end)

That might trigger a Lua error because table.sort expects 'mySortFunction(a, b) == not mySortFunction(b, a)'. Putting a random number in there obviously messes it up.

It is clearly a bias; the same two patterns occur twice as much as the others. I let someone else go into the number theory behind this.

C89 does not specify the rand function to return uniformly distributed random numbers, however, most implementations seem to use a linear congruential generator which is uniform.

I tested it, no error. If you don't like how math.random() generates numbers, you can supplement your own random number generator.