Start learning free

LESSON 315 OF 347 · DYNAMIC PROGRAMMING

Permutations of Given Length in C#: Counting with Factorials

Practice O(n) Read the full explanation

Given a non-negative integer N return the number permutations of length N

Example:

Input: N = 3
Output: 6
Explanation: [
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [2, 3, 1],
    [3, 1, 2],
    [3, 2, 1]
]
Notes: N <= 12
STEP 1 OF 5
    Ctrl + Enter to check

    C# · DYNAMIC PROGRAMMING

    Permutations Of Given Length in C#, explained

    Problem overview

    The method CountPermutations receives an integer n and returns the number of permutations of length n: the ways to arrange the numbers 1 to n in a row, using each exactly once. For n = 3 there are 6: 123, 132, 213, 231, 312 and 321. The notes say n is at most 12.

    Approach: choose the first element, then arrange the rest

    To build a permutation of length i, pick its first element. There are i choices. Whichever one you pick, the remaining i - 1 numbers can be arranged in as many ways as a permutation of length i - 1. So the count for length i is i times the count for length i - 1.

    That recurrence is the factorial: dp[i] = i * dp[i - 1]. It needs a starting value. The empty permutation (length 0) is exactly one arrangement, so dp[0] = 1, which matches 0! = 1. From there, dp[1] = 1 * 1 = 1, dp[2] = 2 * 1 = 2 and dp[3] = 3 * 2 = 6.

    Starting from length 0 instead of 1 also covers n = 0, where the table has only index 0.

    Here is the recurrence on n = 3. Choosing 1 first leaves the numbers 2 and 3 to arrange, which can be done in 2 ways (123 and 132). Choosing 2 first also leaves two numbers and 2 ways (213 and 231), and choosing 3 first gives 312 and 321. Three choices times two arrangements each is 6. Notice that the rest of the permutation is a permutation of a smaller set, and only the size of that set matters for the count, not which numbers are in it. This is why one table indexed by length is enough.

    Step by step

    1. Create the table as an int[] of size n + 1, so that index n exists.
    2. Set dp[0] to 1, the single empty permutation.
    3. Loop from 1 to n inclusive, filling lengths in increasing order so dp[i - 1] is always ready.
    4. Multiply: dp[i] = i * dp[i - 1].
    5. Return dp[n].

    The solution in C#

    class Solution {

    public int CountPermutations(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] = i * dp[i - 1];
        }
        return dp[n];
    }
}

    C# details worth knowing:

    • Why the limit is 12. 12! is 479,001,600, which fits in an int (maximum 2,147,483,647). 13! is 6,227,020,800, which doesn't. C# arithmetic on int is unchecked by default, so the product wraps around silently instead of failing: computing 13! this way produces 1,932,053,504, a wrong answer with no error. Use long for larger inputs, which holds up to 20!.
    • Zero-filled arrays. A new int[] is all zeros, so every entry except dp[0] is overwritten by the loop before it is read.
    • A table is optional. A single running product would do the same job in constant space. The array keeps the recurrence visible.

    Reading the table

    For n = 5 the finished table is [1, 1, 2, 6, 24, 120]. Each entry is the previous one times its own index: 2 = 2 * 1, 6 = 3 * 2, 24 = 4 * 6 and 120 = 5 * 24. The values grow quickly, which is the reason the notes cap n at 12.

    Edge cases and common mistakes

    • n = 0. The loop doesn't run and the method returns dp[0], which is 1.
    • n = 1. The loop runs once and gives 1 * 1 = 1.
    • Base case 0. If dp[0] were left at its default 0, every product would be 0.
    • Loop bound. With i < n the last entry is never filled, and the method returns 0.
    • Going past 12. The result silently overflows, as shown above.

    Testing

    • n = 0 gives 1.
    • n = 3 gives 6.
    • n = 12 gives 479001600.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free