LESSON 322 OF 348 · DYNAMIC PROGRAMMING

Permutations With K Inversions in Kotlin: 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

KOTLIN · DYNAMIC PROGRAMMING

Permutations With K Inversions in Kotlin, explained

Problem overview

The function countPermutations(n, k) returns how many permutations of the numbers 1 to n have exactly k inversions. An inversion is a pair of positions (i, j) with i < j where the earlier value is larger than the later one, so p(i) > p(j). The identity permutation [1, 2, 3] has no inversions, and the fully reversed [3, 2, 1] has all three possible pairs inverted.

For n = 4 and k = 2 the answer is 5. For example, [1, 3, 4, 2] has the inversions (3, 2) and (4, 2), and [2, 1, 4, 3] has (2, 1) and (4, 3). The notes give N <= 12, and k can be at most n * (n - 1) / 2, the number of pairs.

Approach: insert the largest element last

Trying all permutations works for tiny n but costs n! steps, which is 479,001,600 permutations for n = 12, each needing a count of its inversions. Dynamic programming gets there with a small table.

Let dp[i][j] be the number of permutations of length i with exactly j inversions. To build a permutation of length i + 1, take one of length i and insert the new largest value, i + 1, somewhere. Because the new value is larger than everything else, it forms an inversion with every element that ends up after it and with none of the elements before it. Putting it at the very end adds 0 inversions, one slot further left adds 1, and putting it at the very front adds i.

So each permutation of length i with j inversions produces i + 1 permutations of length i + 1, one for each slot, with j, j + 1, up to j + i inversions. Different slots give different permutations, and every permutation of length i + 1 comes from exactly one smaller permutation (remove the largest value), so adding the counts is correct with no double counting.

Counts above k can never lead back down to k, since inserting never removes an inversion. The table therefore only needs columns up to k, and the range of new counts is capped there.

Here is the idea on the smallest interesting case. The permutations of length 2 are [1, 2] with 0 inversions and [2, 1] with 1. Inserting 3 into [1, 2] gives [1, 2, 3], [1, 3, 2] and [3, 1, 2], with 0, 1 and 2 inversions. Inserting 3 into [2, 1] gives [2, 1, 3], [2, 3, 1] and [3, 2, 1], with 1, 2 and 3 inversions. So length 3 has 1, 2, 2 and 1 permutations for 0, 1, 2 and 3 inversions.

Step by step

Create the table with n + 1 rows and k + 1 columns. Row i is for length i, and column j is for j inversions.
Seed length 1. Set dp[1][0] to 1: the single permutation [1] has no pairs and so no inversions. The rest of row 1 stays 0.
Loop over i from 1 to n - 1 with 1 until n. Each pass fills row i + 1 from row i, so the last pass fills row n.
Loop over j from 0 to k with 0..k. Each dp[i][j] permutations will be extended.
Find the highest reachable count. Store minOf(j + i, k) in hi: the largest new count is j + i, and anything beyond k is irrelevant.
Loop over j1 from j to hi. These are the inversion counts the extended permutations can have.
Add the counts. Each permutation counted in dp[i][j] yields exactly one permutation of length i + 1 with j1 inversions, so add dp[i][j] to dp[i + 1][j1].
Return dp[n][k].

The solution in Kotlin

class Solution {
    fun countPermutations(n: Int, k: Int): Int {
        val dp = Array(n + 1) { IntArray(k + 1) }
        dp[1][0] = 1
        for (i in 1 until n) {
            for (j in 0..k) {
                val hi = minOf(j + i, k)
                for (j1 in j..hi) {
                    dp[i + 1][j1] += dp[i][j]
                }
            }
        }
        return dp[n][k]
    }
}

The Kotlin details worth a closer look:

Table construction. Array(n + 1) { IntArray(k + 1) } runs the lambda once per row, so the rows are separate arrays, each filled with zeros. val dp only fixes which array dp names; its cells can still change.
Ranges. 1 until n excludes n, while 0..k and j..hi include their upper end. Both ends of j..hi are used on purpose: j is the "insert at the end" case and hi the furthest slot allowed.
minOf. It is a standard-library function that returns the smaller of its arguments, here two Int values.
Int does not overflow here. The largest value in any cell for n = 12 is well under two billion. For example, countPermutations(12, 33) returns 25598186.

Complexity

Time: O(n * k * n), that is O(n² * k). For each of the n lengths and each of the k + 1 counts, the innermost loop runs at most i + 1 times. With n <= 12 and k <= 66 that is only a few thousand steps.

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

Edge cases and common mistakes

k = 0. Only the sorted permutation qualifies, so countPermutations(3, 0) returns 1.
The maximum k. Only the reversed permutation has every pair inverted, so countPermutations(3, 3) and countPermutations(4, 6) both return 1.
n = 1. countPermutations(1, 0) returns 1. The loop 1 until 1 is empty, and the seed cell is already the answer.
n = 0. The table then has a single row, so the write to dp[1][0] throws ArrayIndexOutOfBoundsException. The notes' examples use positive n; if you want to handle 0, return early.
Forgetting the cap. Without minOf(j + i, k), the write to dp[i + 1][j1] can run past the last column.
Starting the inner range at 0. Extending a permutation never removes an inversion, so j1 starts at j, not at 0.

Testing

n = 4, k = 2 gives 5.
n = 4, k = 5 gives 3.
n = 5, k = 3 gives 15.
n = 3, k = 0 gives 1.
n = 4, k = 6 gives 1.

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

Start learning free