Start learning free

LESSON 340 OF 414 · DYNAMIC PROGRAMMING

Permutations of Given Length in Scala: Factorial with a DP Table

Practice O(n) Read the full explanation

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
    Ctrl + Enter to check

    SCALA · DYNAMIC PROGRAMMING

    Permutations Of Given Length in Scala, explained

    Problem overview

    The method countPermutations receives an Int n and returns how many permutations of length n exist. A permutation of length n is an arrangement of the numbers 1 to n in some order, 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 statement guarantees n is at most 12.

    The task is to count them, not to list them. The count grows very quickly, so a loop that only counts is far cheaper than generating every arrangement.

    Approach: choose the first element, then arrange the rest

    To build a permutation of length i, first choose which of the i numbers goes in the first position. After that, the remaining i - 1 numbers fill the remaining i - 1 positions, and the number of ways to arrange them is the same as the number of permutations of length i - 1. Every choice of first element leads to the same number of arrangements, so

    count(i) = i * count(i - 1)

    This is the factorial: count(i) is i!. The recurrence needs a starting value. A permutation of length 0 is the empty arrangement, and there is exactly one of those, so count(0) = 1. From it, count(1) = 1 * 1 = 1, count(2) = 2, count(3) = 6 and so on.

    Filling a table from the smallest length upward ensures that the value a step needs, count(i - 1), is always ready. That is the core of dynamic programming, and this problem is its simplest form.

    Step by step

    1. Create the table. dp is a new Array[Int] of size n + 1, so index n exists. Entry i will hold the number of permutations of length i. The array starts filled with zeros.
    2. Set the base case. dp(0) = 1. Starting at length 0 rather than 1 also covers n = 0, where the array has only index 0.
    3. Loop over the lengths. for (i <- 1 to n) fills the table in increasing order. For n = 0 the range is empty and the loop does nothing.
    4. Apply the recurrence. 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 Scala

    class Solution {
    def countPermutations(n: Int): Int = {
        val dp = new Array[Int](n + 1)
        dp(0) = 1
        for (i <- 1 to n) {
            dp(i) = i * dp(i - 1)
        }
        return dp(n)
    }
}

    The Scala details worth a closer look:

    • Int is 32 bits. The largest value allowed by the statement, 12!, is 479,001,600 and fits. 13! is 6,227,020,800, which doesn't fit, and the method returns 1,932,053,504 for n = 13, because overflow wraps silently without any error. That is the reason for the limit of 12. A Long would go up to 20.
    • The order of operands. i * dp(i - 1) multiplies an Int by an Int, so the result is an Int and wraps if it is too large. Changing the order doesn't change that.
    • val fixes the name, not the contents. dp is a val, but dp(i) = ... changes one element of the array.
    • Round brackets and ranges. Scala reads array elements with dp(i). In 1 to n, the end n is included, while 1 until n would stop before it.
    • Zeros by default. A new Array[Int] holds zeros, so any entry that is read before it is written gives 0, not an error. The loop order prevents that here.

    Complexity

    Time: O(n). The loop runs n times and each pass does one multiplication.

    Space: O(n). The table has n + 1 entries. Each step reads only the previous one, so a single running product would use O(1) space.

    Edge cases and common mistakes

    • n = 0. The method returns 1, the empty permutation. Because the table has index 0 and the loop is empty, nothing goes out of range.
    • n = 1. The loop runs once and gives 1 * dp(0) = 1.
    • Starting with dp(0) = 0. Every later entry would be 0, since each one is a product that includes the base case.
    • Array too small. Using size n instead of n + 1 leaves no room for dp(n).
    • Looping with until. 1 until n never fills dp(n), so the method returns 0 for n greater than 0.
    • Adding instead of multiplying. Writing i + dp(i - 1) counts something else entirely. The choices multiply, because each choice of first element is combined with every arrangement of the rest.
    • Values above 12. The statement stops at 12, because larger inputs overflow Int.

    Testing

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