Secret Santa – Generating ‘valid’ permutations

What you’re looking for is called a derangement (another lovely Latinate word to know, like exsanguination and defenestration).

The fraction of all permutations which are derangements approaches 1/e = approx 36.8% — so if you are generating random permutations, just keep generating them, and there’s a very high probability that you’ll find one within 5 or 10 selections of a random permutation. (10.1% chance of not finding one within 5 random permutations, every additional 5 permutations lowers the chance of not finding a derangement by another factor of 10)

This presentation is pretty down-to-earth and gives a recursive algorithm for generating derangements directly, rather than having to reject permutations that aren’t derangements.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)