Start learning free

LESSON 324 OF 348 · DYNAMIC PROGRAMMING

Swap Permutations in TypeScript: A Dynamic Programming Recurrence

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

    TYPESCRIPT · DYNAMIC PROGRAMMING

    Swap Permutations in TypeScript, explained

    Problem overview

    The method countPermutations(n) counts the permutations of 1 to n that you can reach from [1, 2, ..., n] by swapping pairs of items, where each item may take part in at most one swap. Zero swaps is allowed, so the starting arrangement counts.

    For n = 3 the answer is 4: the original [1, 2, 3], plus the three arrangements with exactly one swap, [1, 3, 2], [2, 1, 3] and [3, 2, 1]. Two swaps are impossible, because after one swap only one item is left unused, and a swap needs two different items. The notes ask for n from 3 to 12.

    Approach: where does the last item go?

    Enumerating all n! permutations and testing each is hopeless for larger n. A recurrence is much cheaper. Let dp[i] be the answer for length i, and look at item i:

    • It is never swapped. It stays in place, and the other i - 1 items can be arranged in dp[i - 1] ways.
    • It is swapped with one of the other items. There are i - 1 choices of partner. Both items are then used up, and the remaining i - 2 items can be arranged in dp[i - 2] ways.

    The two cases never overlap, so dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]. These permutations are the ones that undo themselves when applied twice, known as involutions, and this is their standard recurrence.

    The base cases are dp[1] = 1 (one item can only stay) and dp[2] = 2 (stay, or swap the two). Then dp[3] = 2 + 2 * 1 = 4, dp[4] = 4 + 3 * 2 = 10 and dp[5] = 10 + 4 * 4 = 26.

    Step by step

    1. Create the table. Make an array of n + 1 zeros so that dp[i] is the answer for length i. Index 0 is unused.
    2. Set the base cases. dp[1] is 1 and dp[2] is 2, written together in one statement.
    3. Loop from 3 to n, so each value is built from two values that are already known.
    4. Apply the recurrence to compute dp[i].
    5. Return dp[n].

    The solution in TypeScript

    class Solution {
    countPermutations(n: number): number {
        const dp: number[] = new Array(n + 1).fill(0);
        ((dp[1] = 1), (dp[2] = 2));
        for (let i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
        }
        return dp[n];
    }
}

    TypeScript details worth knowing:

    • The comma operator. The line ((dp[1] = 1), (dp[2] = 2)); is two assignments joined by a comma. The comma evaluates both, left to right, and produces the value of the last one. Each assignment is itself an expression with a value, so the whole line has the value 2, which is thrown away. Two separate statements would do the same job.
    • fill(0) is required. new Array(n + 1) alone has empty slots, and arithmetic on an empty slot gives NaN. With fill(0) every slot is a real number.
    • const and the array. The name dp can't be reassigned, but its elements can.
    • Writing past the end grows the array. For n = 1 the array has two slots, and dp[2] = 2 quietly adds a third. The function still returns dp[1], which is 1.
    • Plain numbers. A TypeScript number is a double, so for n = 12 the result, 140152, is exact and there is no overflow to think about.

    Complexity

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

    Space: O(n). The array has n + 1 entries. The recurrence only looks at the last two values, so two variables would reduce this to O(1).

    Edge cases and common mistakes

    • Forgetting the factor i - 1. Item i can pair with any of the other i - 1 items. Using dp[i - 1] + dp[i - 2] would give 3 for n = 3 instead of 4.
    • Using dp[i - 1] in the swap case. After a swap, two items are used up, so two fewer items remain.
    • Small inputs. n = 1 returns 1 and n = 2 returns 2. They come straight from the base cases.
    • Treating this as n!. For n = 4 there are 24 permutations but only 10 swap permutations. A rotation such as [2, 3, 4, 1] needs a swap chain in which an item moves twice, so it is not counted.

    Testing

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