Start learning free

LESSON 340 OF 414 · DYNAMIC PROGRAMMING

Permutations of Given Length in Rust: Counting with a DP Table

Practice O(n) Read the full explanation

Given a non-negative integer N return the number of permutations of length N

Example:

Input: N = 3
Output: 6
Explanation: [
    [1, 2, 3],
    [1, 3, 2],
    [2, 1, 3],
    [2, 3, 1],
    [3, 1, 2],
    [3, 2, 1]
]
Notes: N <= 12
STEP 1 OF 5
    Ctrl + Enter to check

    RUST · DYNAMIC PROGRAMMING

    Permutations Of Given Length in Rust, explained

    Problem overview

    The function count_permutations takes n and returns how many permutations of length n exist: orderings of the numbers 1 through n, each used once. The statement limits N to 12.

    For n = 3 the permutations are [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] and [3, 2, 1], so the answer is 6.

    Approach: choose the first element, then arrange the rest

    Let dp[i] be the number of permutations of length i. To build one, pick its first element: there are i choices. Whatever was picked, the remaining i - 1 elements can be arranged in dp[i - 1] ways, since only their number matters and not which values they are. So:

    dp[i] = i * dp[i - 1]

    This is the factorial, i!. The base case is dp[0] = 1: there is exactly one permutation of nothing, the empty one. Starting from length 0 instead of 1 has a second benefit, covered below: it makes n = 0 work with no special case.

    Step by step

    1. Create dp as vec![0i32; n + 1], declared let mut. The starting code has already shadowed n with a usize, so it can serve as both a size and an index. The extra slot makes index n exist.
    2. Set dp[0] = 1. This is 0! = 1. Even when n is 0 and the vector has only index 0, the final lookup works.
    3. Loop over 1..=n, so each length is computed after the one before it.
    4. Multiply: dp[i] = (i as i32) * dp[i - 1]. The index i is a usize, and Rust doesn't multiply an i32 by a usize, so i is converted first.
    5. Return dp[n] as the final 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[0] = 1;
        for i in 1..=n {
            dp[i] = (i as i32) * dp[i - 1];
        }
        dp[n]
    }
}

    The Rust details worth a closer look:

    • Shadowing. let n = n as usize; declares a new variable that hides the i32 parameter. The converted value is used from then on, which is cleaner than casting at every use.
    • The suffix in 0i32. It fixes the element type of the vector. The multiplication must be between two i32 values, and the suffix makes the type explicit.
    • Casting with as. n as usize would turn a negative n into an enormous number, so the code relies on the statement's non-negative input. i as i32 is safe because i is at most 12.
    • Overflow. 12! = 479,001,600 fits in an i32, and 13! = 6,227,020,800 does not. That is why the statement stops at 12. In an optimized build, going past that would wrap silently, and in a debug build it would panic.

    Complexity

    Time: O(n). One multiplication per length.

    Space: O(n). The table has n + 1 entries. Keeping only the running product would use O(1).

    Edge cases and common mistakes

    • N = 0. Returns 1. The vector has one entry, the loop 1..=0 is empty, and dp[0] is 1.
    • N = 1. Returns 1, since 1 * dp[0] is 1.
    • Starting the table at 1. With dp[1] = 1 as the base, n = 0 would need a separate case or it would index past the end.
    • Multiplying by i - 1. That gives 0 at i = 1 and zeroes everything after it. The number of choices for the first element is i.
    • Forgetting the cast. i * dp[i - 1] doesn't compile, because usize and i32 are different types.

    Testing

    • n = 0 gives 1.
    • n = 1 gives 1.
    • n = 3 gives 6.
    • n = 12 gives 479001600.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free