Start learning free

LESSON 348 OF 414 · DYNAMIC PROGRAMMING

Swap Permutations in Scala: Dynamic Programming

Practice O(n) Read the full explanation

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

A swap permutation is obtained from the identical permutation (1, 2, 3, ..., n) by applying the swap operation multiple times

A swap operation consists of picking two different items from the permutation and swapping them

You are allowed to swap an item at most once

Example:

Input: n = 3
Output: 4
Explanation: [
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [3, 2, 1]
]
We start from [1, 2, 3], which is a swap permutation
because we  applied 0 swap operations, and we apply
one of the following swaps:
[1, 2, 3] => [1, 3, 2]
[1, 2, 3] => [2, 1, 3]
[1, 2, 3] => [3, 2, 1]
Notice that we can only apply one swap operation
because we are left with only 1 item that is not swapped.
For larger values of n we can have multiple chained operations.
Notes: 3 <= n <= 12
STEP 1 OF 5
    Ctrl + Enter to check

    SCALA · DYNAMIC PROGRAMMING

    Swap Permutations in Scala, explained

    Problem overview

    The method countPermutations(n) counts the permutations of 1 to n that can be reached from (1, 2, ..., n) by a series of swaps, where each item takes part in at most one swap. Zero swaps is allowed, so the identity permutation counts. The notes limit n to the range 3 to 12.

    For n = 3 the answer is 4: [1, 2, 3] with no swaps, and the three single swaps [1, 3, 2], [2, 1, 3] and [3, 2, 1]. Two swaps would need four different items, and a third item would have to be swapped twice, so nothing more is possible.

    The rule "each item is swapped at most once" means the swaps never overlap. A swap permutation is a set of disjoint pairs that trade places, while all the other items stay where they are.

    Approach: ask what happens to the last item

    Let dp(i) be the number of swap permutations of length i. Look at item i, the last one:

    • It is never swapped. It stays in place and the other i - 1 items are arranged in any valid way: dp(i - 1) possibilities.
    • It is swapped with another item. There are i - 1 choices for the partner. Both items are then used up, and the remaining i - 2 items are arranged in dp(i - 2) ways. That gives (i - 1) * dp(i - 2) possibilities.

    The two cases cover every permutation exactly once, so dp(i) = dp(i - 1) + (i - 1) * dp(i - 2). The recurrence needs two starting values. One item can only stay in place, so dp(1) = 1. Two items can stay or swap, so dp(2) = 2.

    The table grows as follows:

    n:      1  2  3   4   5   6   7
dp(n):  1  2  4  10  26  76  232

    For example, dp(4) = dp(3) + 3 * dp(2) = 4 + 6 = 10. These counts are known as the involution numbers: the permutations that are their own inverse, which is exactly what a set of disjoint swaps produces.

    Step by step

    1. Create the array with Array.fill(n + 1)(0). Index 0 is unused, so index i holds the count for length i.
    2. Set the base cases dp(1) = 1 and dp(2) = 2. The lesson writes both on one line, separated by a semicolon.
    3. Loop over 3 to n. Starting at 3 is safe because the two values it needs, dp(1) and dp(2), are already set.
    4. Apply the recurrence to fill dp(i).
    5. End the method with dp(n).

    The solution in Scala

    class Solution {
    def countPermutations(n: Int): Int = {
        val dp = Array.fill(n + 1)(0)
        dp(1) = 1; dp(2) = 2
        for (i <- 3 to n) {
            dp(i) = dp(i - 1) + (i - 1) * dp(i - 2)
        }
        dp(n)
    }
}

    Some Scala details in this code:

    • Array.fill(n + 1)(0) builds an Array[Int] of n + 1 cells, each set to 0. The size goes in the first parentheses and the value in the second.
    • A semicolon can separate two statements on one line. Scala normally ends a statement at the line break, but dp(1) = 1; dp(2) = 2 is valid because of the semicolon.
    • val and the array's contents. val dp means the name can't be pointed at another array, but the cells can still be changed, which is why dp(1) = 1 works.
    • Ranges. 3 to n includes n. When n is 3 the loop runs once, and a range such as 3 to 2 is empty.
    • No return needed. The last expression of the method body, dp(n), is its value.

    Complexity

    Time: O(n). One loop, with constant work per iteration.

    Space: O(n). The array has n + 1 cells. Since each value needs only the previous two, two variables would be enough.

    Edge cases and common mistakes

    • Counting the identity. Zero swaps is a valid swap permutation. That is why dp(2) is 2 and not 1.
    • Multiplying by i instead of i - 1. The partner for item i can be any of the other i - 1 items. Using i would let an item swap with itself, and dp(3) would come out as 5 instead of 4.
    • Using dp(i - 1) twice. After a swap, two items are used, so the rest has i - 2 items, not i - 1.
    • Small n. The notes promise n >= 3. With n = 2 the method returns 2, but with n = 1 the array has only two cells, so dp(2) = 2 throws an ArrayIndexOutOfBoundsException.
    • Overflow. Int wraps silently, but the largest answer in range, countPermutations(12), is 140152. There is no overflow risk at that size.
    • Starting the loop at 2. It would overwrite dp(2) with dp(1) + 1 * dp(0), which is 1, because index 0 is unused and holds 0.

    Testing

    • n = 3 gives 4.
    • n = 4 gives 10.
    • n = 5 gives 26.
    • n = 8 gives 764.
    • n = 12 gives 140152.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free