Start learning free

LESSON 307 OF 338 · DYNAMIC PROGRAMMING

Permutations of Given Length in Go: Factorials with a DP Table

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

    GO · DYNAMIC PROGRAMMING

    Permutations Of Given Length in Go, explained

    Problem overview

    The function countPermutations takes an int n and returns how many permutations of length n exist: the ways to arrange the numbers 1 to n in a row, using each exactly once. For n = 3 there are 6: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] and [3, 2, 1]. The lesson's 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. Once it is placed, the remaining i - 1 positions are filled with the remaining i - 1 numbers, and the number of ways to do that is the same question for a smaller size. So the count for i is i times the count for i - 1.

    This is the factorial recurrence, i! = i * (i - 1)!, written as a DP table. The base case is length 0. There is exactly one way to arrange nothing, the empty permutation, so dp[0] = 1. From there dp[1] = 1 * 1 = 1, dp[2] = 2 * 1 = 2, dp[3] = 3 * 2 = 6, and so on.

    Step by step

    1. Create the table with make([]int, n+1), so index n exists. Every entry starts at 0.
    2. Set dp[0] = 1. Starting at length 0 instead of 1 also covers n = 0, where the table has only index 0.
    3. Loop with i from 1 while i <= n, so entries are filled in increasing order and dp[i-1] is always ready.
    4. Compute dp[i] = i * dp[i-1]: i choices for the first element times the arrangements of the other i - 1.
    5. Return dp[n].

    The solution in Go

    func countPermutations(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        dp[i] = i * dp[i-1]
    }
    return dp[n]
}

    The Go details worth a closer look:

    • Slices from make. make([]int, n+1) gives a slice of length n + 1 filled with zeros. A fixed-size array would not do, because the size n is only known when the function runs.
    • The loop. Go's only loop keyword is for. The clause i := 1; i <= n; i++ needs no parentheses, and i exists only inside the loop.
    • No overflow at this size. int is 64 bits in Go 1.22 on 64-bit systems, and the largest value here, 12!, is 479001600. Go's int keeps wrapping silently when it overflows, so the table would go wrong without any error for n around 21 and above, since 21! no longer fits in 64 bits. The lesson's limit of 12 is far from that.
    • Mixing types. i * dp[i-1] multiplies two int values. Go does no implicit conversion between numeric types, so mixing in an int64 or float64 would need an explicit conversion.

    What the table looks like

    For n = 5 the loop fills the table like this: dp starts as [1, 0, 0, 0, 0, 0]. After the iteration for i = 1 it is [1, 1, 0, 0, 0, 0], then i = 2 gives 2, i = 3 gives 6, i = 4 gives 24 and i = 5 gives 120. The finished table is [1, 1, 2, 6, 24, 120], and the function returns its last entry. Every number was computed once and then reused by the next step, which is the saving that dynamic programming brings: the larger answer never recomputes the smaller ones.

    The statement lists the permutations, but the function only counts them. Producing all of them takes time proportional to n * n!, because each permutation has n numbers, while counting needs only n multiplications. That difference is why the recurrence matters: the count is cheap even when the list would be far too long to write out.

    Complexity

    Time: O(n), one multiplication per step. Space: O(n) for the table. Each entry depends only on the one before it, so a single running product would use O(1) space.

    Edge cases and common mistakes

    • n = 0. The loop does not run, and the function returns dp[0], which is 1: the empty permutation counts.
    • n = 1. dp[1] = 1 * dp[0] = 1.
    • Starting dp[0] at 0. Every entry is a multiple of the previous one, so the whole table stays 0.
    • Using i < n. The loop stops one entry early, and dp[n] remains 0.
    • Multiplying by i-1. That counts the arrangements with one fewer choice for the first element. The first position has i candidates.

    Testing

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