Permutation Coefficient Problem

The problem, simply

You get two numbers, n and k. Count the ways to pick k things out of n and put them in order. This number is called P(n, k).

The formula is P(n, k) = n! / (n - k)!, which is the same as n x (n - 1) x ... x (n - k + 1), a product of k numbers. If k > n the answer is 0. Many versions ask for the answer modulo 1,000,000,007.

A story to remember it

Picture it

Examples

Way 1: the simple way

Think about the last kid, kid number n.

• Either that kid gets no prize. Then all k prizes go to the other n - 1 kids: P(n - 1, k) ways.
• Or that kid gets one of the k prizes (k choices), and the other k - 1 prizes go to the other n - 1 kids: k x P(n - 1, k - 1) ways.

So P(n, k) = P(n - 1, k) + k x P(n - 1, k - 1), with P(n, 0) = 1 and P(n, k) = 0 when k > n. Write it as a recursive function.

class Solution {
    static final long MOD = 1_000_000_007L;

    public long nPr(int n, int k) {
        if (k == 0) return 1;           // no prizes: one way
        if (k > n) return 0;            // more prizes than kids
        long lastSkipped = nPr(n - 1, k);           // last kid gets nothing
        long lastWins = k * nPr(n - 1, k - 1) % MOD; // last kid gets one of k prizes
        return (lastSkipped + lastWins) % MOD;
    }
}

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

Way 2: the clever way

Hand out the prizes one at a time and keep a running answer. P(n, j) = P(n, j - 1) x (n - j + 1): the jth prize can go to any kid who does not have a prize yet, and there are n - j + 1 of them.

1. Start with ways = 1 (zero prizes).
2. For j = 1 to k: ways = ways x (n - j + 1).
3. Return ways.

Each step fills the next box of a small row of answers, and only the last box is needed, so one number is enough.

class Solution {
    static final long MOD = 1_000_000_007L;

    public long nPr(int n, int k) {
        if (k > n) return 0;
        long ways = 1;                          // zero prizes handed out
        for (int j = 1; j <= k; j++) {
            ways = ways * (n - j + 1) % MOD;    // kids still without a prize
        }
        return ways;
    }
}

How long it takes: k multiplications, O(k). Extra room: one number, O(1).

Way 3: the full table

Some interviewers ask for the textbook table version, which turns Way 1 into a table. Row i holds P(i, j) for every j, and each cell uses the cell above it and the cell above and to the left.

class Solution {
    static final long MOD = 1_000_000_007L;

    public long nPr(int n, int k) {
        if (k > n) return 0;
        long[][] P = new long[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            P[i][0] = 1;                                   // no prizes
            for (int j = 1; j <= Math.min(i, k); j++) {
                P[i][j] = (P[i - 1][j] + j * P[i - 1][j - 1]) % MOD;
            }
        }
        return P[n][k];
    }
}

This takes O(n * k) time and O(n * k) room (or O(k) with one row filled from right to left). It is slower than Way 2, but it gives every P(i, j) at once, which helps when you have many questions.

Watch out for

• k > n must return 0, and k = 0 must return 1.
• Take the modulo after each multiply, not only at the end.
• Do not mix it up with C(n, k), which ignores order. P(n, k) = C(n, k) x k!.

What interviewers ask next

• How is it related to combinations? Choosing the group ignores order, C(n, k), then arranging the group gives k! orders. So P = C x k!.
• Answer many questions P(n, k) mod p fast. Precompute factorials and inverse factorials up to the largest n once. Then each answer is fact[n] x invFact[n - k], which is O(1).
• What if p is small, smaller than n? Then n! is 0 modulo p and the inverse trick breaks. The plain product from Way 2 still works, because it never divides.

Remember this

Grown-up words: handing out prizes in order is a permutation, P(n, k) is the permutation coefficient, the recursive rule is a Pascal style recurrence, the running answer is 1D dynamic programming, and the fast many question trick uses modular inverses.