LESSON 341 OF 415 · DYNAMIC PROGRAMMING

Permutations of Given Length in Swift: Counting with a dp Array

Given a non-negative integer N return the number of 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

Guided

Ctrl + Enter to check

Permutations Of Given Length in Swift, explained

Problem overview

The method countPermutations receives a length n and returns how many permutations of length n exist, meaning the number of ways to arrange the numbers 1 to n in a row, each used exactly once. For n = 3 the six arrangements are [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] and [3, 2, 1]. The notes limit n to 12.

Only the count is needed, so no permutation is ever generated.

Approach: choose the first element, then arrange the rest

To build a permutation of length i, choose its first element: there are i choices. Whichever one is picked, the remaining i - 1 positions are filled with the remaining i - 1 numbers, and the number of ways to do that is the same as the number of permutations of length i - 1. The two choices multiply:

dp[i] = i * dp[i - 1]

This is the definition of the factorial, i!. The base case is length 0: there is exactly one way to arrange nothing, the empty arrangement, so dp[0] is 1. That gives dp[1] = 1, dp[2] = 2, dp[3] = 6, and so on. Starting from length 0 also makes n = 0 work with no special case.

The example shows it. The six arrangements for n = 3 fall into three groups by their first number: two start with 1, two with 2 and two with 3. Inside each group, the other two numbers can be placed in 2 orders, which is dp[2]. So dp[3] = 3 * 2 = 6. The same split gives dp[4] = 4 * 6 = 24, and the table grows quickly: dp[10] is 3628800.

Step by step

Create the table: a var array dp of n + 1 zeros, with [Int](repeating: 0, count: n + 1). The size makes index n exist, and var allows the loop to write into it.
Set the base case: dp[0] = 1.
Loop over the lengths with i in 1..<(n + 1). The range stops before its end value, so n + 1 makes the loop include n. Going in increasing order guarantees that dp[i - 1] is ready when dp[i] needs it.
Multiply: dp[i] = i * dp[i - 1].
Return dp[n].

The solution in Swift

class Solution {
    func countPermutations(_ n: Int) -> Int {
        var dp = [Int](repeating: 0, count: n + 1)
        dp[0] = 1
        for i in 1..<(n + 1) {
            dp[i] = i * dp[i - 1]
        }
        return dp[n]
    }
}

Swift details worth knowing:

Empty ranges are fine; inverted ones are not. For n = 0 the loop range is 1..<1, which is empty, so the body is skipped and dp[0] is returned. A range such as 1..<0 would crash, but n + 1 is never below 1 for a non-negative n.
Overflow stops the program. Swift's Int is 64 bits, and an overflowing multiplication crashes instead of wrapping. It doesn't matter here: 12! is 479001600, and 20! is the largest factorial that fits in an Int, so the lesson's limit of 12 is far from it. Computing 21! would crash.
Mixing types. Both i and dp[i - 1] are Int, so the multiplication needs no conversion.

Complexity

Time: O(n), one multiplication per length.

Space: O(n), for the table. Each entry only needs the one before it, so a single running product would use O(1).

Edge cases and common mistakes

n = 0. The answer is 1, the empty permutation.
n = 1. The answer is 1.
Setting dp[0] to 0. Every entry would be 0, since each one is a multiple of the previous.
Adding instead of multiplying. dp[i - 1] + i counts something else; the choices at each position multiply.
A table of size n. Index n would be out of range, and the program would crash.

Testing

n = 0 gives 1.
n = 3 gives 6.
n = 12 gives 479001600.

Keep going with SwiftAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free