Start learning free

LESSON 324 OF 348 · DYNAMIC PROGRAMMING

Swap Permutations in Kotlin: A Recurrence with 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

    KOTLIN · DYNAMIC PROGRAMMING

    Swap Permutations in Kotlin, explained

    Problem overview

    The function countPermutations(n) counts the permutations of 1, 2, ..., n that you can reach from the identity permutation by swapping pairs of items, where each item may take part in at most one swap. Zero swaps is allowed, so the identity itself counts.

    For n = 3 the answer is 4: [1, 2, 3] with no swap, and the three single swaps [1, 3, 2], [2, 1, 3] and [3, 2, 1]. A second swap is impossible, because after one swap only one item is left unused, and a swap needs two. For larger n, several disjoint swaps can be chained. The notes say 3 <= N <= 12.

    Approach: ask what happens to the last item

    Generating all permutations and testing each one is slow, since there are n! of them. A recurrence is faster. Let dp[i] be the answer for length i, and 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, giving dp[i - 1] permutations.
    • It is swapped with one of the other i - 1 items. That partner is used up along with item i, and the remaining i - 2 items are arranged in any valid way, giving dp[i - 2] permutations for each of the i - 1 possible partners.

    The two cases are disjoint, so the totals add: dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]. The base cases are dp[1] = 1, because one item can only stay put, and dp[2] = 2, because two items either stay or swap. The recurrence gives dp[3] = 2 + 2 * 1 = 4, which matches the example. The same numbers count the permutations that are their own inverse, called involutions.

    Step by step

    1. Create dp as an IntArray of size n + 1, so that dp[n] is a valid index. Index 0 goes unused.
    2. Set the base cases dp[1] = 1 and dp[2] = 2.
    3. Loop i over 3..n. Each value needs the two before it, which are already filled.
    4. Apply the recurrence in the loop body.
    5. Return dp[n].

    The solution in Kotlin

    class Solution {
    fun countPermutations(n: Int): Int {
        val dp = IntArray(n + 1)
        dp[1] = 1; dp[2] = 2
        for (i in 3..n) {
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]
        }
        return dp[n]
    }
}

    The Kotlin details worth a closer look:

    • IntArray(n + 1). It creates n + 1 zeros. val only stops you from pointing dp at a different array, so assigning to its elements is fine.
    • The semicolon. Kotlin statements normally end at the line break. A semicolon lets you put two statements on one line, as in dp[1] = 1; dp[2] = 2.
    • Ranges. 3..n includes n, which is what you want here. If n is less than 3 the range is empty and the loop body never runs.
    • Int is enough. The value for n = 12 is 140152, nowhere near the Int limit, so no Long is needed.

    Complexity

    Time: O(n). The loop runs n - 2 times with constant work in each.

    Space: O(n). The array holds n + 1 integers. Each value depends only on the previous two, so two variables could replace the array.

    Edge cases and common mistakes

    • Small n. The notes promise n >= 3. With n = 1 the array has size 2, and the line dp[2] = 2 throws ArrayIndexOutOfBoundsException. n = 0 fails earlier, at dp[1] = 1.
    • Forgetting the multiplier. Writing dp[i - 1] + dp[i - 2] gives the Fibonacci numbers. The factor i - 1 counts the choices of partner.
    • Using i instead of i - 1. Item i can't swap with itself, so there are only i - 1 partners.
    • Counting different swap orders separately. Swapping items 1 and 2 and then 3 and 4 gives the same permutation as the other order. The recurrence counts permutations, not sequences of swaps.

    Testing

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