Shuffling

[Santos]

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:

shuffling.zip

(131.45 KiB) Downloaded 39 times

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.

0CPfY0t.png (2.56 KiB) Viewed 456 times

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.

KPs4IaJ.png (3.44 KiB) Viewed 456 times

Let's say we picked the circle. Let's move it to the other side!

01jkOFO.png (4.51 KiB) Viewed 456 times

And now we can just repeat. Pick a random shape, and move it to the other side.

yvwTLq0.png (3.22 KiB) Viewed 456 times

Let's pick the pentagon.

YMel1kf.png (3.24 KiB) Viewed 456 times

And now the square.

KY5y4MI.png (2.56 KiB) Viewed 456 times

And, well, we don't have a choice, let's move the triangle over too.

yqMM3wt.png (2.51 KiB) Viewed 456 times

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.

QB5bd7z.png (4.03 KiB) Viewed 456 times

And then, move it over to the left.

fD7mouT.png (2.63 KiB) Viewed 456 times

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.

ETEu47P.png (3.2 KiB) Viewed 456 times

Let's pick the pentagon.

ZmbSoau.png (3.01 KiB) Viewed 456 times

And now the square.

lbtxxyo.png (2.37 KiB) Viewed 456 times

And hey, turns out the last shape is already there.

yF0KkX3.png (2.36 KiB) Viewed 456 times

So, that example was the same thing as the one before. If that wasn't clear, here's both of them side by side:

QBIm3g4.png (19.95 KiB) Viewed 456 times

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.

K9ZaGS1.png (3.43 KiB) Viewed 456 times

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.

Sq0bRbQ.png (3.19 KiB) Viewed 456 times

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!

gKphpvk.png (4.48 KiB) Viewed 456 times

f0JwxOy.png (3.01 KiB) Viewed 456 times

Now let's pick another random shape from the area on the right, the square, and swap it with the triangle under the flag.

5QYCqRv.png (3.05 KiB) Viewed 456 times

And there's only one left, and it's already in the only place it can be, so we're done!

yF0KkX3.png (2.36 KiB) Viewed 456 times

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:

bDNtyJr.png (11.67 KiB) Viewed 456 times

Let's see how this works with a run through!

So let's say we give this function our table of shapes...

H2AMESz.png (11.54 KiB) Viewed 456 times

"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...

s7WLigP.png (27.77 KiB) Viewed 456 times

And the second...

vu4PCMz.png (29.56 KiB) Viewed 456 times

And the third and final iteration...

6TVs6vW.png (30.5 KiB) Viewed 456 times

And the table has been shuffled!

AWDCu7G.png (2.36 KiB) Viewed 456 times

[micha]

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.

[Ref]

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!

[Roland_Yonaba]

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.

[Inny]

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

[Kyle]

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

Code: Select all

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

[Santos]

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.

Code: Select all

function fisheryates(t)
	for i = 1, #t - 1 do
		local r = math.random(i, #t)
		t[i], t[r] = t[r], t[i]
	end
end

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

results = {}

for i = 1, 50000 do
	t = {'a', 'b', 'c'}
	fisheryates(t)
	key = table.concat(t)
	results[key] = results[key] or 0
	results[key] = results[key] + 1
end

for k, v in pairs(results) do
	print(k..'\t'..v)
end

print()

results = {}

for i = 1, 50000 do
	t = {'a', 'b', 'c'}
	tablesort(t)
	key = table.concat(t)
	results[key] = results[key] or 0
	results[key] = results[key] + 1
end

for k, v in pairs(results) do
	print(k..'\t'..v)
end

Output:

Code: Select all

cba	8376
abc	8238
cab	8449
bca	8346
bac	8266
acb	8325

acb	6305
cab	6033
abc	6153
bac	12478
cba	6466
bca	12565

Still, pretty nice for one line of code!

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!

[Kyle]

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.

[Boolsheet]

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.

[Kyle]

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