Start learning free

LESSON 323 OF 347 · DYNAMIC PROGRAMMING

Swap Permutations in C#: A Simple 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

    C# · DYNAMIC PROGRAMMING

    Swap Permutations in C#, explained

    Problem overview

    The method CountPermutations(int n) counts the permutations of 1 to n that you can build from [1, 2, ..., n] by repeatedly swapping two items, with one rule: each item may be swapped at most once. Doing no swaps is allowed, so the starting permutation counts.

    For n = 3 the answer is 4: the original [1, 2, 3], and one swap each of the pairs (2, 3), (1, 2) and (1, 3), giving [1, 3, 2], [2, 1, 3] and [3, 2, 1]. A second swap would need two unused items, and after one swap only one item is left. Larger inputs allow several independent swaps, for example [2, 1, 4, 3] for n = 4.

    Approach: decide what happens to the last item

    Since each item moves at most once, and a swap moves both of its items, the result is a set of disjoint pairs that trade places while every other item stays where it is. Counting those arrangements is a classic recurrence.

    Look at item i, the last of the first i items. It is in one of two situations:

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

    The two cases do not overlap, so dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]. These numbers also count the permutations that are their own inverse, which are called involutions.

    Worked from the base cases: one item can only stay, so dp[1] = 1. Two items can stay or swap, so dp[2] = 2. Then dp[3] = 2 + 2 * 1 = 4, matching the example, and dp[4] = 4 + 3 * 2 = 10.

    Step by step

    1. Create the table. An int[] of length n + 1 lets dp[i] be indexed directly by i. Index 0 is never used. C# zero-fills the array.
    2. Set the base cases dp[1] = 1 and dp[2] = 2, which the recurrence cannot produce on its own.
    3. Loop from 3 to n inclusive. Each value needs the two before it, and they are ready by then.
    4. Apply the recurrence in each iteration, as derived above.
    5. Return dp[n].

    The solution in C#

    class Solution {

    public int CountPermutations(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1; dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
        }
        return dp[n];
    }
}

    A few C# notes:

    • Two statements on one line. dp[1] = 1; dp[2] = 2; is legal, since C# separates statements by semicolons, not line breaks.
    • Array size and bounds. new int[n + 1] has valid indexes 0 to n. The code assigns dp[2] directly, so n must be at least 2, or the array is too short and C# throws IndexOutOfRangeException. The lesson's range starts at 3.
    • Overflow stays away. The values grow fast: dp[12] is 140,152 and still tiny next to int.MaxValue. For much larger n, int arithmetic would wrap silently instead of failing.

    Complexity

    Time: O(n). One pass with constant work per step.

    Space: O(n). The table has n + 1 entries. Each value uses only the previous two, so two variables would also work, and the space would drop to O(1).

    Edge cases and common mistakes

    • Forgetting the multiplier. Writing dp[i - 1] + dp[i - 2] gives Fibonacci numbers. Item i has i - 1 possible partners, so dp[i - 2] must be multiplied by i - 1.
    • Counting the original arrangement. The identity permutation counts as one. That is why dp[1] is 1 and not 0.
    • Counting swaps in different orders separately. Swapping (1, 2) then (3, 4) gives the same result as (3, 4) then (1, 2). The recurrence counts resulting permutations, not sequences of operations.
    • Starting the loop too early. With i = 2, the recurrence would read dp[0], which is 0, and overwrite the correct base case.

    Testing

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