LESSON 346 OF 414 · DYNAMIC PROGRAMMING

Permutations With K Inversions in Rust: Dynamic Programming

Practice O(n * k) Read the full explanation

Given two non-negative integers N and K, return the number of permutations of length N with exactly K inversions

An inversion is a pair of indices (i, j) with i < j and p(i) > p(j)

Example:

Input: N = 4, K = 2
Output: 5
Explanation: [
    [1, 3, 4, 2],
    [1, 4, 2, 3],
    [2, 1, 4, 3],
    [2, 3, 1, 4],
    [3, 1, 2, 4],
]

Notes:
N <= 12
K <= N * (N - 1) / 2

STEP 1 OF 9

Guided

Ctrl + Enter to check

Permutations With K Inversions in Rust, explained

Problem overview

The function count_permutations receives n and k and returns how many permutations of the numbers 1 to n have exactly k inversions. An inversion is a pair of positions i < j where the value at i is larger than the value at j: a pair that is out of order.

For n = 4 and k = 2 the answer is 5. The five permutations are [1, 3, 4, 2] (out-of-order pairs 3 and 2, 4 and 2), [1, 4, 2, 3], [2, 1, 4, 3], [2, 3, 1, 4] and [3, 1, 2, 4]. Each has exactly two pairs that are out of order.

Approach: insert the largest value

Trying all n! permutations and counting inversions in each is far too slow as n grows. Instead, build permutations by growing them. Take a permutation of the values 1 to i and insert the new largest value, i + 1, at some position. The new value is bigger than everything before it, so it forms an inversion with every element that ends up to its right, and with nothing to its left.

That gives a neat rule. Put the new value at the very end and it adds 0 inversions. Put it one place from the end and it adds 1, and so on, up to i new inversions when it goes to the very front. So each permutation of length i with j inversions produces exactly i + 1 permutations of length i + 1, with j, j + 1, ..., j + i inversions, one each. Every permutation of length i + 1 arises this way exactly once, because removing the largest value gives back the smaller permutation.

Here is the idea at work. Row 2 is [1, 1]: the permutations [1, 2] and [2, 1] have 0 and 1 inversions. Each of them gets the value 3 inserted in one of three slots, which adds 0, 1 or 2 inversions. The one with 0 inversions spreads to counts 0, 1 and 2; the one with 1 spreads to counts 1, 2 and 3. Adding up, row 3 is [1, 2, 2, 1]: six permutations in total, as expected for 3!.

So let dp[i][j] be the number of permutations of length i with exactly j inversions, and push each count forward into the range j to j + i of the next row.

Step by step

Convert the inputs to usize. Vectors are indexed with usize, so n and k are shadowed by usize copies.
Create the table. It has n + 1 rows of k + 1 zeros each, as i32. Row i is for permutations of length i.
Seed length 1. The only permutation of one element has no inversions, so dp[1][0] is 1.
Loop over lengths i from 1 to n - 1. Each pass builds row i + 1.
Loop over inversion counts j from 0 to k.
Skip empty cells. A zero has nothing to pass on. This only saves work; the result is the same without it.
Loop over the new counts j1, from j up to min(j + i, k). Counts above k can never lead back down, so the range is capped at k.
Add the count forward: dp[i + 1][j1] += dp[i][j].
Return dp[n][k].

The solution in Rust

impl Solution {
    fn count_permutations(n: i32, k: i32) -> i32 {
        let n = n as usize;
        let k = k as usize;
        let mut dp = vec![vec![0i32; k + 1]; n + 1];
        dp[1][0] = 1;
        for i in 1..n {
            for j in 0..=k {
                if dp[i][j] == 0 {
                    continue;
                }
                for j1 in j..=std::cmp::min(j + i, k) {
                    dp[i + 1][j1] += dp[i][j];
                }
            }
        }
        dp[n][k]
    }
}

The Rust details worth knowing:

Shadowing. let n = n as usize; declares a new n that hides the i32 parameter for the rest of the function. The old value is not changed; the name just refers to the new one.
The 0i32 suffix. It fixes the cell type to i32, the return type, so no later line needs a cast.
as usize on a negative number. Casting a negative i32 to usize gives an enormous value, not an error. The lesson's inputs are non-negative, so this doesn't arise here.
continue. It ends the current pass of the innermost loop only, here the j loop, and moves on to the next j.
Inclusive ranges. j..=std::cmp::min(j + i, k) includes its upper end. std::cmp::min takes two values of the same type, and both are usize here.
Overflow. With n at most 12, every cell is at most 12! = 479001600, the number of all permutations, which fits in an i32. In an optimized build an overflow would wrap silently, but here none can happen.

Complexity

Time: O(n * k * n), that is O(n²k). There are n lengths and k + 1 counts, and the innermost loop runs at most i + 1 times, which is at most n.

Space: O(n * k). The table has (n + 1) * (k + 1) cells.

Edge cases and common mistakes

Zero inversions. k = 0 gives 1 for every n: only the sorted permutation.
Maximum inversions. n = 4, k = 6 gives 1: only the fully reversed permutation. A k above n * (n - 1) / 2 gives 0, for example n = 4, k = 7.
Single element. n = 1, k = 0 gives 1. The loop 1..1 is empty and dp[1][0] is returned.
Forgetting the cap. Without min(..., k), dp[i + 1][j1] can index past the end of the row and panic.
Wrong insertion count. A permutation of length i has i + 1 insertion slots, giving 0 to i new inversions. Using j + i - 1 as the top end misses the front slot.

Testing

n = 4, k = 2 gives 5.
n = 3, k = 0 gives 1.
n = 4, k = 6 gives 1.
n = 4, k = 7 gives 0.
n = 5, k = 4 gives 20.
n = 12, k = 66 gives 1.

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

Start learning free