LESSON 321 OF 347 · DYNAMIC PROGRAMMING

Permutations With K Inversions in C#: Dynamic Programming

Practice O(n * k) Read the full explanation

Given two non-negative integers N and K, return the number 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],
    [1, 4, 3, 2],
    [2, 1, 4, 3],
    [3, 1, 2, 4],
]

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

STEP 1 OF 7

Guided

Ctrl + Enter to check

C# · DYNAMIC PROGRAMMING

Permutations With K Inversions in C#, explained

Problem overview

The method CountPermutations(int n, int k) 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 earlier value is larger than the later one: p[i] > p[j]. The sorted permutation has no inversions, and the fully reversed one has the maximum, n * (n - 1) / 2.

For n = 4 and k = 2 the answer is 5. The five permutations are [1, 3, 4, 2], [1, 4, 2, 3], [2, 1, 4, 3], [2, 3, 1, 4] and [3, 1, 2, 4]. Take [1, 4, 2, 3]: its inverted pairs are (4, 2) and (4, 3), which is exactly two.

Approach: build permutations one value at a time

Listing every permutation takes n! steps, and with n up to 12 that is nearly half a billion permutations, each needing an inversion count. Dynamic programming avoids that by counting without listing.

The key idea is to grow a permutation by inserting the largest value last. Start from any permutation of length i and insert the new value i + 1 into one of the i + 1 possible slots. Because the new value is larger than everything already there, it forms an inversion with exactly the elements to its right. Putting it at the very end adds 0 inversions, one slot further left adds 1, and the very front adds i.

So a permutation of length i with j inversions produces i + 1 distinct permutations of length i + 1, one for each inversion count from j to j + i. Every permutation of length i + 1 arises this way exactly once, by removing its largest value. That gives a table: dp[i, j] is the number of permutations of length i with exactly j inversions.

Step by step

Allocate the table. int[,] is a rectangular two-dimensional array indexed as dp[i, j]. It needs n + 1 rows because row i stands for length i, and k + 1 columns for the counts 0 to k. C# fills a new array with zeros.
Seed the base case. The only permutation of length 1 is [1], with no inversions, so dp[1, 0] = 1.
Loop over lengths. Each pass with index i reads row i and writes row i + 1. The last pass, i = n - 1, fills row n.
Loop over inversion counts j from 0 to k, visiting every cell of the current row.
Loop over the results of the insertion. The new value adds between 0 and i inversions, so the new count j1 runs from j to j + i. Counts above k are never needed, so the upper bound is Math.Min(j + i, k).
Add the counts. Each of the dp[i, j] permutations gives exactly one permutation with j1 inversions, so dp[i + 1, j1] += dp[i, j].
Return dp[n, k].

Here is the table for n = 4, k = 2, columns being the inversion counts 0, 1 and 2:

length 1:  1  0  0
length 2:  1  1  0
length 3:  1  2  2
length 4:  1  3  5

In row 3, the count 2 can come from a row-2 permutation with 0 inversions (the new value adds 2), with 1 inversion (adds 1) or with 2 inversions (adds 0). Row 2 holds 1, 1 and 0 for those counts, so the cell is 1 + 1 + 0 = 2. In row 4 the count 2 is 1 + 2 + 2 = 5, the answer.

The solution in C#

class Solution {

    public int CountPermutations(int n, int k) {
        int[,] dp = new int[n + 1, k + 1];
        dp[1, 0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                for (int j1 = j; j1 <= Math.Min(j + i, k); ++j1) {
                    dp[i + 1, j1] += dp[i, j];
                }
            }
        }
        return dp[n, k];
    }
}

Some C# details:

int[,] is not int[][]. A rectangular array is one block with a fixed shape, created in a single expression and indexed with a comma. A jagged array is an array of arrays that you index as dp[i][j] and whose rows you allocate one by one.
Zero-initialisation. Every cell starts at 0, so the += in the innermost loop works without a separate setup pass.
The loop condition is re-evaluated. Math.Min(j + i, k) is recomputed on every iteration. That costs almost nothing here, and it keeps the bound in the same place as the loop.
No overflow for n <= 12. The counts add up to at most 12! = 479,001,600, which fits in an int. Beyond that, integer arithmetic would silently wrap, so a larger n would call for long or a modulus.

Complexity

Time: O(n * n * k). There are n - 1 passes over lengths, k + 1 values of j, and at most i + 1 values of j1 for each. Since k is at most about n * n / 2, this is small for n = 12.

Space: O(n * k). The table holds (n + 1) * (k + 1) integers. Each row depends only on the previous one, so two rows would be enough if memory mattered.

Edge cases and common mistakes

k = 0. Only the sorted permutation qualifies, so the answer is 1. The table gives that: column 0 stays 1 in every row.
k at the maximum. Only the reversed permutation has n * (n - 1) / 2 inversions, so CountPermutations(4, 6) is 1.
n = 1. The length loop never runs and dp[1, 0] is returned, which is 1 for k = 0.
n = 0. The table then has a single row, so writing dp[1, 0] throws an IndexOutOfRangeException. The lesson's tests use positive lengths.
Row confusion. Writing into row i while reading row i double-counts. The pass for length i must write row i + 1.
Wrong upper bound. Using j + i + 1 allows one more inversion than the new value can create. A new value inserted into a permutation of length i has i + 1 slots, giving 0 to i new inversions.

Testing

n = 4, k = 2 gives 5.
n = 3, k = 1 gives 2: [2, 1, 3] and [1, 3, 2].
n = 3, k = 0 gives 1.
n = 4, k = 6 gives 1.
n = 5, k = 3 gives 15.

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