The Desk Drawer Problem or Why It Is Good to Know What You Are Doing

Life writes the best stories, they say. And if the moral of this story also fits one's own professional life, why not tell it? You will learn why it is easier to think ahead about what you are doing, and what role a curious son, mathematics, and permutations play in this in the following article.

As soon as my son Lorenz comes home from school, he independently starts his homework. He sits at a desk about 100 years old with a velvet top, which my grandfather also worked on. Recently, Lorenz asked me how many different ways the drawers of the desk can be swapped.

To know this: The desk has 9 drawers, all of the same size. Thus, all drawers can be swapped among each other. There are 9 places available for 9 drawers. For the mathematicians among us, it is probably easy to find the corresponding solution here. But firstly, not all of us are equipped with Archimedean or Keplerian abilities, and secondly, the journey to the solution is, as is well known, the goal. So it is here.

3 Drawers, 3 Drawers and a Few Questions

To illustrate the problem in a simpler variant, we will initially settle for 3 drawers, to later transfer it to the desk with 9 drawers.

We have 3 drawers labelled A, B, and C, as well as 3 places labelled 1, 2, and 3. First, we remove all drawers from the desk. If we now want to place drawer A in the desk, all 3 places are still free. Thus, there are 3 possibilities for placing the drawer. Next, when we want to insert drawer B into the desk, only 2 places remain, as one place is already occupied by drawer A. Finally, there is only one place left for drawer C. This methodology can be applied a few times – depending on which place we start with drawer A. The table below lists all possibilities:

Mathematically speaking, this is referred to as permutations, i.e., swaps. The number of possible swaps for 3 drawers is calculated as follows: 3*2*1 = 6. Alternatively, one can simply write 3! (read: 3 factorial).

Now we transfer the problem to a desk with 4 drawers (A, B, C, D): For drawer A, we have 4 places left, for drawer B, 3 places remain, and so on. It is now easily evident that we can calculate the number using 4*3*2*1 = 4! = 24. For the desk with 9 drawers, there are thus 362,880 possible swaps. And no matter how many drawers there may be, this system can be applied to any desk, no matter how large. In other words: For any number 'n' of drawers, the number of swaps can be calculated using n!.

Below you will find a table that shows the number of swaps depending on the drawers in overview:

Source: Wolfram Alpha

All clear – or not?

So far, so good, so clear. I took the liberty of implementing the Heap Algorithm, which can be used to list all permutations, in ABAP on one of our test systems. Subsequently, I had the program determine all swaps for 11 drawers. However, I did not output the individual swaps, and it still took about 1.5 minutes to determine them all.

Admittedly, taking this path is practically pointless, as the number of swaps can be quickly calculated. If swaps are not visualised at all, the program provides no real added value. What the program does show very nicely is (and now we are slowly approaching the moral of the story) that even for a small input set, high runtimes can occur.

It is important to be clear that not all problems are easy or quick to solve. Before attempting to solve a problem or just programming wildly, one should first analyse the problem or task and assess whether it is even feasible or solvable. The often applied solution method in practice of 'listing all possibilities and then searching for the right one' is rarely ideal. It would be better to construct the solution using targeted methods.

From Maths to (Professional) Life

And so we are back at our desk: No matter how you turn it, and no matter which algorithm you choose in this case, the number of permutations will of course not decrease. In many cases, however, a single solution is sufficient for a problem (e.g., just one swap). That there are many other solutions (all swaps) is good, but not necessary.

Listing all possible swaps falls under combinatorics, which is a part of discrete mathematics. Discrete mathematics encompasses many areas of computer science and algorithms, and having a fundamental knowledge in our profession can be beneficial. Not for you, not for me, not for my son. Just as he asked me, you can also ask me if you want to know more about it. Or if you want to know how the desk with its drawers found its way into our four walls. But that is another story altogether.