Do the Knuth Shuffle

Introduction

That Donald Knuth is a genius is an axiom that I doubt any user of TeX-SX would seriously quibble with. He invented TeX, after all, making him simultaneously the cat’s pyjamas and the bee’s knees. I would guess that many here are also aware of his standing in the computer science community, though we may be a little unsure as to exactly what the “computer science community” actually is in this context. But for myself, and perhaps many here, that’s where we stop. As a theoretical mathematician, specialising in geometry and the like, I have only the vaguest knowledge of what someone like Knuth would work with.

So it was a nice surprise the other day when looking for a solution to a problem that I encountered something that sometimes is called the Knuth shuffle (it goes by other names as well, and goes back to Fisher and Yates in 1938 according to Wikipedia). As the problem that this solved happened to be a TeX one, this happy juxtaposition of Knuthness seems on topic for this blog.

I’ll start by outlining the problem I was trying to solve and then show how the Knuth shuffle provides an integral part of the solution.

The Problem

The original problem did not come up on TeX-SX but on a mailing list that I’m on. It wasn’t specifically TeX-oriented, but once I saw the problem I realised that TeX could be used to solve it. Here’s the problem (somewhat rephrased):

To produce a grid of shapes (of a specified size) where each shape is either a red triangle or a black square. The number of each shapes that appear should be fixed, but otherwise their placement should be (pseudo)random.

In the original problem, the number of each shape should be half the total (modulo an even/odd issue) and it was also requested that it be possible to sneak in a single red square in some grids.

The Easy Parts

The original description did not specify a particular format or program or anything to be used and also asked if it was possible to do this programmatically, which was what made me think of TeX. The shapes are easy enough for any of the graphics packages available, and placing them in a grid is similarly simple. I happen to know TikZ best so chose to do it that way, but I can imagine that it would be equally easy in PSTricks or one of the others.

In TikZ, creating a grid of shapes is not hard. One method is to devise a family of appropriate node styles and then iteratively place them at the grid coordinates using \foreach loops. Another is to use a matrix. In my final solution, I used a matrix. The actual matrix command was:

The key matrix of shapes sets up a few defaults which are worth mentioning. What may surprise TikZ aficionados is that this (by default) produces a 4-by-5 matrix. Where do all the matrix cells come from? There’s only one in the above!

Here’s where. The matrix of shapes installs some code to be run in every empty cell (via the execute at empty cell key). This code then generates all of the other cells. The point of doing it this way is that it is easier to specify the number of the cells by a couple of keys rather than by a number of ampersands and slashes. In each of those generated cells is the code for drawing a node of the appropriate colour and shape.

(Incidentally, the \ line is essential; it’s to do with how the \matrix command knows when a matrix ends.)

So getting the grid of shapes is easy enough. What’s a little more complicated is getting the choice of shape to be random.

The Hard Part

The difficulty with the random part of this problem is the constraint: the number of each shape is predetermined. So it isn’t a matter of flipping a coin at each cell and putting a red triangle or black square accordingly. We have to decide on a random arrangement first, and then lay them out accordingly.

It’s not hard to find out the number of possible arrangements, given the numbers of each shape, and then generating a (pseudo)random integer is also easy (or, at least, already implemented in pgfmath). The difficult part is linking that number to a specific arrangement. One could simply have a lookup list, but the problem with that is that the parameters are not fixed for all time. They are only fixed for a specific run. So we would need a robust method of listing the arrangements in order to pick one at random.

I will freely admit that I didn’t spend a lot of time on that particular problem: it looked too much like hard work. Instead, I reasoned as follows. Imagine that we had not two families of shapes but a list of distinct shapes to arrange. Then the number of arrangements would be the same as the number of permutations of those objects. So we could take our families of shapes and mark each shape to make it distinct (for example, write a number on each shape). Then we pick a random arrangement of our marked shapes, arrange our shapes, and then erase the markings. This would leave us with a randomly chosen arrangement of our original shapes.

The catch with this is that there is more than one way of getting the same arrangement. The beauty of it is that the number of ways of getting any one arrangement is the same as any other arrangement. So if we choose the original permutation uniformly at random then each arrangement of our unmarked shapes is equally likely to occur.

Rather than proving this (it isn’t hard, but if you understand enough maths to understand the proof then you probably don’t need to see the proof), let me give an example. Suppose we have two shapes, let’s call them 0 and 1, and two of each. Thus our “bag” is “(0 1 0 1)”. Let’s list all the arrangements, there are 6 of them.

• (0 0 1 1)

• (0 1 0 1)

• (0 1 1 0)

• (1 0 0 1)

• (1 0 1 0)

• (1 1 0 0)

Now let’s label the objects them to make them different. We can label them “(0 1 2 3)”, with “2” being a copy of “0” and “3” a copy of “1”. There are 24 permutations of 4 objects; let us list them together with the arrangement of “(0 1 0 1)” that they represent.

• (0 0 1 1): (0 2 1 3), (2 0 1 3), (0 2 3 1), (2 0 3 1)

• (0 1 0 1): (0 1 2 3), (2 1 0 3), (0 3 2 1), (2 3 0 1)

• (0 1 1 0): (0 1 3 2), (2 1 3 0), (0 3 1 2), (2 3 1 0)

• (1 0 0 1): (1 0 2 3), (1 2 0 3), (3 0 2 1), (3 2 0 1)

• (1 0 1 0): (1 0 3 2), (1 2 3 0), (3 0 1 2), (3 2 1 0)

• (1 1 0 0): (1 3 0 2), (1 3 2 0), (3 1 0 2), (3 1 2 0)

So when we label the objects to make them distinct, each of the arrangements appears 4 times. Thus if we pick a permutation at random, we have four chances of getting each arrangement. As this is the same for each arrangement, we have the same chance of getting each arrangement.

This may seem like a daft thing to do: we’ve made our problem more complicated and substituted the word “permutation” for “arrangement”.

The point of this is that permutations are very common subjects of study and so I figured that I had a higher chance of getting a relevant search hit for random permutation than random arrangement¹ .

Sure enough, the top link for random permutation is the corresponding page on Wikipedia which explains a very nice algorithm for producing a random permutation given that you can produce random integers.

The Algorithm

Imagine you wanted to produce a random permutation of, say, “(0 1 2 3)”. You have at your disposal a random number generator that can generate uniformly an integer between a given minimum and maximum (these can vary). The first step is easy: we need to pick a first number in our permutation. This has to be a number between 0 and 3 (inclusive) so we set our generator to produce one. It did so, and produced “2”.

The next step is less elegant. We need to produce the second number in our permutation. This has to be drawn from the set “0 1 3”. Given that we can only produce integers from intervals, the simplest way to do this is to produce an integer between 0 and 2, and then remember to replace “2” by “3”. We do this, and get “0”.

The third (and final) step is the messiest of them all. Using the above method, we pick a one of “0” or “1” at random and then remember that “0” means “1” and “1” means “3”.

The problem with the above is that the substitutions depend on what’s gone before so we have to keep track of them all, and the substitutions keep changing in each run.

Fortunately, there is another way. And what is so beautiful about this algorithm is not just its simplicity, but the fact that it is very much “of the real world”. There’s no fancy mathematics: it’s a very concrete solution.

Instead of permuting numbers, let’s permute something a bit more interesting: wild animals at the zoo. We have a lion, a tiger, a leopard, and a cheetah in our zoo. We’d like to move them around from enclosure to enclosure to make it look as though we have an Interesting Zoo that Changes Every Week. So the animals are already in enclosures, and we’d like to randomly shift them around.

We start at the first cage. As it’s the first one, we make a completely random choice of animal to put in it. That is, we select one animal from all the available cages and put it in that cage. Let’s suppose it was the tiger.

Now we have a problem. The cage was already occupied, say by the lion. So we need to get the lion out before we put the tiger in. We do so, but now we have the lion outside. That’s not a good situation! So although we don’t know where the lion will eventually be, we’d like to put it somewhere safe (for us!) for the time being. There’s an obvious place to put it: the cage recently vacated by the tiger.

In summary, we’ve swapped the lion and the tiger. In more detail, we’ve picked a cage and an animal to go in that cage. That selection has also resulted in another animal (which was in the first cage) and another cage (which the first animal was in). Then we’ve swapped the two animals.

Now we have the lion, leopard, and cheetah to distribute between three cages. But this is precisely the situation we started in, except with one less cage and one less animal. So we can just repeat: select a cage, randomly choose an animal to go in that cage, then swap the animals.

With a little more precision, what we’ve done is the following. We lay out the things that we want to permute in some ordering. Then we go along the list of things in that ordering. Let’s say it’s from left to right. As we come to each place, we choose at random one object from those places that lie to its right (including that particular place). Then we swap the object that is currently there with the one that we’ve chosen.

It is simple to see that this produces the required uniform choice of permutation. We have a uniform choice for the first object of all objects, then a uniform choice for the second object of all the remaining objects, and so on down the line.

The elegance of this algorithm is not really in the choosing part, but in the storage. By swapping objects, we make it easy to know what objects we have left to choose from since it is always those “to the right”.

The Implementation

Implementing this in TeX is quite straight forward. I don’t claim to have the best or most elegant solution, but certainly this is a way to do it. Let’s say we have four objects: lion, tiger, leopard, and cheetah. We start by initialising our data.

Now we begin our shuffle. In the real application, I used the pgfmath library to generate the random numbers. In this, I’ll imagine that there’s some expandable random number generator built in to TeX that expands to a random number uniformly between bounds (inclusively) as given by the arguments.

(Incidentally, that < should really be a < but the HTML escaper escaped too much again.)

There’s one final neat piece of this algorithm. The above code needs a temporary holding place for swapping the two entries. However, if the objects in the final arrangement are to be used one at a time, instead of swapping the objects then we use one of them and put the other in its place. Thus this algorithm can be put in place while the array is actually being used, rather than having to be done beforehand. Thus, the above loop could be:

The Grid

And thus, after all that, a piece of code that arranges shapes on a grid at random, subject to the fact that the number of each shape is constant.

The package file can be downloaded from my website and a full working example is: