For the past few years, I’ve created technological solutions to a problem clearly in need of the might of modern technology: choosing secret santa gift recipients for my girlfriend’s immediate family. (She’s proposed a solution involving a hat.)
In previous years, I’ve taken the easy and obvious approach: generate a random permutation, and see if anyone ends up giving themselves a gift. If they do, try again.
This approach has two flaws:
- It may take multiple tries to get a valid permutation. It could take three, four, or even more attempts! We could be delayed by milliseconds waiting to know the results.
- It’s way too efficient.
Fortunately, I found a way around both of these problems: generate all permutations that don’t fix any elements, then choose a random one. I’ve been poking around with learning Common Lisp, so I decided to write a solution in it.
I haven’t figured out exactly how inefficient this is, but I’m guessing it grows exponentially with the size of the input set. The number of permutations of the set is obviously exponential (Stirling’s approximation), and eliminating the permutations that fix an element doesn’t take out too many of the branches:
| Input size | Non-fixing permutations |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 2 |
| 4 | 9 |
| 5 | 44 |
| 6 | 265 |
| 7 | 1854 |
| 8 | 14833 |
| 9 | 133496 |
Conclusion: It’s a good thing her family isn’t too big.
The fact that you do things like this for fun confuses me. How did we become friends, again???
It’s a good thing I think nerds are fun… Neal, you may have achieved an entirely new level of geekdom.
So I shouldn’t ask you to make a solution for my family’s 12-person exchange? We have an added degree of difficulty- they try to keep spouses from buying for one another. Go, Neal, go!
Hee. So in talking with one of my old CS professors yesterday, I discovered that this is a known and well-explored problem: it’s called a derangement.
I’ll have to do more research before I take another crack at this problem. He didn’t seem to think that it would be too difficult to come up with an algorithm to choose a random derangement. I’ll work on it.