A Remarkably Inefficient Gift-Giving Algorithm

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:

  1. 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.
  2. 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.

Make the Web a Quiet Place In Firefox

A combination of three add-ons and a configuration tweak can go a long way toward making the Web a quiet, calm place.


In the NoScript preferences page, go the Advanced tab and select Forbid Macromedia Flash and Forbid other plugins.

Animated GIFs

Unfortunately, some people still feel the need to put animated GIFs up on their web pages. Fortunately, there’s a hidden configuration option that will let you stop them from playing more than once or from playing at all. Go to about:config and find the image.animation_mode preference. Set it to once to let images animate once, or none to prevent them from animating at all. (Kudos to the mozillaZine article on animated images for documenting this.)