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.