Count Derangements (Permutation such that no element appears in its original position)

The problem, simply

You have n things in a row, each in its own spot. Shuffle them so that no thing stays in its own spot. Count how many such shuffles exist. A shuffle like that is called a derangement.

The count gets huge, so judges want it modulo 10^9 + 7.

A story to remember it

Picture it

Examples

Way 1: the simple way

The most obvious try is to list all n! orders and check each one. That is far too slow even for n = 12. The story gives a much better rule, so start from that with plain recursion:

1. D(1) = 0 and D(2) = 1.
2. For bigger n: D(n) = (n - 1) * (D(n - 1) + D(n - 2)).

class Solution {
    static final long MOD = 1_000_000_007L;

    long D(int n) {
        if (n == 1) return 0;                    // your own hat is the only one left
        if (n == 2) return 1;                    // swap
        // first kid picks one of n-1 hats; then swap (n-2 left) or no swap (n-1 left)
        return (n - 1) * ((D(n - 1) + D(n - 2)) % MOD) % MOD;
    }

    public long countDer(int n) {
        return D(n);
    }
}

How long it takes: each call makes two calls, like Fibonacci, so the calls grow up to O(2^n). Extra room: the chain of waiting calls, O(n).

Way 2: the clever way

The two cases from the story, drawn for four kids:

The recursion keeps working out the same D(3). Fill the answers from small to big instead. Each one only needs the two before it, so keep two numbers.

1. Start with prev2 = D(1) = 0 and prev1 = D(2) = 1.
2. For i from 3 to n: cur = (i - 1) * (prev1 + prev2), then slide: prev2 = prev1, prev1 = cur.
3. Return prev1 (or 0 when n == 1).

class Solution {
    public long countDer(int n) {
        final long MOD = 1_000_000_007L;
        if (n == 1) return 0;
        if (n == 2) return 1;
        long prev2 = 0;   // D(1)
        long prev1 = 1;   // D(2)
        for (int i = 3; i <= n; i++) {
            long cur = (i - 1) * ((prev1 + prev2) % MOD) % MOD;
            prev2 = prev1;                       // slide the window forward
            prev1 = cur;
        }
        return prev1;
    }
}

How long it takes: one step per kid, O(n). Extra room: two numbers, O(1).

Watch out for

• D(1) = 0, not 1. And if the judge defines D(0), it is 1 (the empty shuffle).
• Take the modulo inside: (i - 1) * (prev1 + prev2) can overflow a long if prev1 + prev2 is not reduced first.
• Return prev1, not cur. When n is 1 or 2 the loop never runs.

What interviewers ask next

• Is there another rule? Yes: D(n) = n * D(n - 1) + (-1)^n. It needs only one earlier value.
• What fraction of all shuffles are derangements? It quickly gets close to 1/e, about 0.368. In fact D(n) is n! / e rounded to the nearest whole number. Quant interviews love this one: "n people grab random hats, what is the chance nobody gets their own?"
• Exactly k people get their own hat? Choose who they are, then derange the rest: C(n, k) * D(n - k).
• Expected number of people who get their own hat? Exactly 1 for any n, because each person has a 1/n chance and there are n people.
• Where does the formula come from without the story? Inclusion and exclusion: D(n) = n! * (1 - 1/1! + 1/2! - ... + (-1)^n / n!).

Remember this

Grown-up words: a shuffle with nobody in their own spot is a derangement, a shuffle is a permutation, the two cases are a case split for a recurrence, and keeping two numbers is space optimization.