Start learning free

LESSON 348 OF 414 · DYNAMIC PROGRAMMING

Swap Permutations in Rust: A Two-Term 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

Guided

Ctrl + Enter to check

RUST · DYNAMIC PROGRAMMING

Swap Permutations in Rust, explained

Problem overview

The function count_permutations receives n and returns the number of swap permutations of length n. A swap permutation is what you get from (1, 2, ..., n) by repeatedly picking two different items and swapping them, with the rule that each item may take part in at most one swap.

For n = 3 the answer is 4: the original [1, 2, 3] (no swaps), then [1, 3, 2], [2, 1, 3] and [3, 2, 1] (one swap each). A second swap isn't possible, because only one untouched item would remain.

Because every item moves at most once, and a swap moves both of its items, each item ends up either in its place or exchanged with exactly one partner. Mathematicians call these permutations involutions: applying them twice gives back the original order.

Approach: ask what happens to the last item

Listing the permutations and checking each one gets slow quickly, so count with a recurrence. Let dp[i] be the answer for length i, and look at item i, the last one. There are two cases, and they don't overlap:

Item i is never swapped. It stays where it is, and the other i - 1 items can be arranged in dp[i - 1] ways.
Item i is swapped with one of the other i - 1 items. There are i - 1 choices of partner. Both items are then used up, which leaves i - 2 items and dp[i - 2] ways to arrange them.

Adding the cases gives dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]. The base cases are dp[1] = 1 (one item can only stay put) and dp[2] = 2 (stay, or swap once). Checking: dp[3] = dp[2] + 2 * dp[1] = 4, which matches the example, and dp[4] = dp[3] + 3 * dp[2] = 10.

For n = 4 you can confirm the 10 by counting directly: the identity (1 way), one swap (6 ways, one for each pair of positions), and two disjoint swaps (3 ways: positions 1-2 with 3-4, 1-3 with 2-4, and 1-4 with 2-3). The sum is 1 + 6 + 3 = 10.

Step by step

Convert n to usize by shadowing, because Rust indexes vectors with usize. Then create dp as a mutable vector of n + 1 zeros of type i32. Index 0 is never used, so index i matches length i.
Write the base cases. Set dp[1] to 1. Set dp[2] to 2 only inside an if n >= 2, so the index exists.
Loop i over 3..=n. Each value uses the two before it, which are already filled.
Apply the recurrence. Compute the sum of the two cases, with i cast to i32 for the multiplication.
Return dp[n] as the last expression.

The solution in Rust

impl Solution {
    fn count_permutations(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = vec![0i32; n + 1];
        dp[1] = 1;
        if n >= 2 {
            dp[2] = 2;
        }
        for i in 3..=n {
            dp[i] = dp[i - 1] + (i as i32 - 1) * dp[i - 2];
        }
        dp[n]
    }
}

The Rust details worth knowing:

Casting precedence. In i as i32 - 1, the cast binds tighter than the subtraction, so it means (i as i32) - 1. Rust never converts between integer types on its own: multiplying a usize by an i32 is a compile error, so the cast is required.
Why not subtract first in usize? Here i is at least 3, so i - 1 is safe either way. In general, a usize subtraction that goes below 0 panics in a debug build and wraps in an optimized one, so casting first, as the lesson does, is the safer habit.
The guard on dp[2]. For n = 1 the vector has only two cells, indexes 0 and 1, so writing to dp[2] would panic with an index out of bounds. The if prevents that.
Empty ranges. For n = 1 or n = 2 the range 3..=n is empty and the loop body never runs. That is a normal, valid range in Rust.
The tail expression. dp[n] has no semicolon, so it is the returned value.

Complexity

The table is filled once, left to right, and each cell reads two earlier cells. No cell is computed twice, which is what makes this fast compared with building every permutation.

Time: O(n). The loop does one constant-size calculation for each length from 3 to n.

Space: O(n). The vector has n + 1 numbers. Only the last two are ever needed, so two variables would reduce this to O(1).

Growth is fast, but it stays inside an i32 for the allowed sizes: for n = 12 the answer is 140152.

Edge cases and common mistakes

Forgetting the multiplier. Writing dp[i - 1] + dp[i - 2] counts a single partner. Item i can pair with any of i - 1 items, so the second term needs the factor i - 1. That mistake gives 3 for n = 3 instead of 4.
Using the wrong index for the second term. After a swap, two items are used, so the rest is dp[i - 2], not dp[i - 1].
Writing dp[2] unconditionally. It panics for n = 1, as described above.
Mixing integer types. (i - 1) * dp[i - 2] without a cast doesn't compile, because i is a usize and dp[i - 2] an i32.
Counting the identity twice. The identity permutation is one of the answers, and the recurrence includes it through the "never swapped" case all the way down to dp[1].

Testing

n = 1 gives 1.
n = 2 gives 2.
n = 3 gives 4.
n = 4 gives 10.
n = 5 gives 26.
n = 12 gives 140152.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free