Start learning free

LESSON 349 OF 415 · DYNAMIC PROGRAMMING

Swap Permutations in Swift: A Recurrence Over Item Positions

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

    SWIFT · DYNAMIC PROGRAMMING

    Swap Permutations in Swift, explained

    Problem overview

    The method countPermutations(_ n: Int) counts the arrangements of 1, 2, ..., n that can be reached from the identity arrangement by swaps, where no item may take part in more than one swap. Zero swaps is allowed, so the identity itself counts.

    For n = 3 the answer is 4: [1, 2, 3], [1, 3, 2], [2, 1, 3] and [3, 2, 1]. After one swap of two items, only one item is left untouched, so there are no more swaps to make. The notes say 3 <= N <= 12.

    Approach: decide what happens to the last item

    Because no item is swapped twice, the swaps never overlap. A swap permutation is therefore a set of disjoint pairs of items that trade places, with every other item staying put. Count them by looking at item i, the last one:

    • It stays in place. The other i - 1 items can be arranged in dp[i - 1] ways.
    • It swaps with one of the other i - 1 items. That choice uses up two items, so the remaining i - 2 are arranged in dp[i - 2] ways.

    These cases are different and cover everything, so dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]. The base cases are dp[1] = 1 (one item can only stay) and dp[2] = 2 (stay, or swap once).

    Check it for n = 3: dp[3] = dp[2] + 2 * dp[1] = 2 + 2 = 4. For n = 4: dp[4] = dp[3] + 3 * dp[2] = 4 + 6 = 10. Those numbers are also the count of involutions, the permutations that are their own inverse, which is the same family of permutations.

    Step by step

    1. Create dp as a var array of n + 1 zeros. Index 0 is unused so that dp[i] means length i.
    2. Set the base cases dp[1] = 1 and dp[2] = 2, in one tuple assignment.
    3. Loop i over 3...n. Each value needs the two before it, and both bases are already set.
    4. Apply the recurrence: dp[i] is dp[i - 1] plus (i - 1) * dp[i - 2].
    5. Return dp[n].

    The solution in Swift

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

    Swift details worth knowing:

    • Tuple assignment. (dp[1], dp[2]) = (1, 2) assigns both elements at once. The left side is a tuple of two array elements, and each one is assigned the matching value. It is the same as two separate assignment lines.
    • Closed range. 3...n includes n. If n is less than 3 this range is invalid, and Swift stops the program instead of quietly skipping the loop. That is acceptable only because the notes promise n >= 3.
    • The array size. The array has n + 1 slots, so dp[2] exists only when n >= 2. For n = 1 the write to dp[2] is out of bounds and the program crashes, because Swift checks every array index.
    • Overflow traps. Int is 64 bits and a too-large result crashes instead of wrapping. The values stay small here: dp[12] is 140152.

    Complexity

    Time: O(n). One loop with a constant amount of work per step.

    Space: O(n). The array holds n + 1 integers. The recurrence only looks two steps back, so two variables would be enough for O(1) space.

    Edge cases and common mistakes

    • Multiplying by i instead of i - 1. Item i has only i - 1 possible partners, because it can't swap with itself.
    • Using dp[i - 1] in the swap case. After a swap, two items are used, so the rest are counted by dp[i - 2].
    • Small n. n = 1 and n = 2 stop the program in this solution. The answers by the recurrence's bases would be 1 and 2, so a version that has to handle them needs to return early.
    • Confusing this with all permutations. There are 6 permutations of 3 items but only 4 swap permutations: the two 3-cycles need chained swaps that reuse an item.

    Testing

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