LESSON 346 OF 414 · DYNAMIC PROGRAMMING

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

Guided

Ctrl + Enter to check

SCALA · DYNAMIC PROGRAMMING

Permutations With K Inversions in Scala, explained

Problem overview

The method 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 where the value at i is larger than the value at j. The notes limit n to 12 and k to at most n * (n - 1) / 2, the number of pairs.

For n = 4 and k = 2 the answer is 5. One of the five permutations is [1, 3, 4, 2]: its inversions are (3, 2) and (4, 2). The sorted permutation has 0 inversions, and the fully reversed one has the maximum, n * (n - 1) / 2.

Trying every permutation costs n! steps, and 12! is 479,001,600 permutations to build and inspect. The lesson counts them with a table instead.

Approach: insert the largest element

Take a permutation of length i and add the number i + 1, the largest so far, in one of the i + 1 possible places. Because the new number is bigger than everything else, it is only ever the larger member of a pair. It creates one new inversion for every element to its right:

placed at the very end, it creates 0 new inversions;
one place further left, it creates 1;
placed at the very front, it creates i.

Each permutation of length i + 1 comes from exactly one permutation of length i and one insertion place: remove the largest number and you get back the shorter permutation. So nothing is counted twice or missed.

Let dp(i)(j) be the number of permutations of length i with exactly j inversions. Every permutation counted in dp(i)(j) produces one permutation with j inversions, one with j + 1, and so on up to j + i. Since only counts up to k matter, the lesson cuts the range at k.

Here is the table for k = 2. Each row lists the counts for 0, 1 and 2 inversions:

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

Row 4 comes from row 3, which is 1, 2, 2. The single permutation with 0 inversions feeds columns 0, 1 and 2 (it can gain 0, 1 or 2). The two with 1 inversion feed columns 1 and 2, and the two with 2 inversions feed column 2 only, because adding any inversions would pass k. Column 2 gets 1 + 2 + 2 = 5.

Step by step

Create the table with Array.ofDim[Int](n + 1, k + 1): a row for each length from 0 to n, a column for each inversion count from 0 to k, all zeros.
Set dp(1)(0) to 1. The single permutation of length 1 has no inversions. The rest of row 1 stays 0.
Loop over the lengths with 1 until n. Pass i reads row i and fills row i + 1, so the last pass fills row n.
Loop over the inversion counts with 0 to k.
Compute the upper bound hi = math.min(j + i, k): inserting the new element adds at most i inversions, and anything above k is not needed. Then loop with j1 over j to hi.
Add dp(i)(j) into dp(i + 1)(j1). Each insertion place gives a different permutation, so the counts simply add up.
Return dp(n)(k) as the last expression.

The solution in Scala

class Solution {
    def countPermutations(n: Int, k: Int): Int = {
        val dp = Array.ofDim[Int](n + 1, k + 1)
        dp(1)(0) = 1
        for (i <- 1 until n) {
            for (j <- 0 to k) {
                val hi = math.min(j + i, k)
                for (j1 <- j to hi) {
                    dp(i + 1)(j1) += dp(i)(j)
                }
            }
        }
        dp(n)(k)
    }
}

Some Scala details in this code:

The last expression is the result. The method ends with dp(n)(k) and no return. A for loop is a statement that produces no useful value, so the final line is what the method hands back.
math.min is scala.math.min, available without an import. It takes two numbers and returns the smaller.
Ranges. 1 until n excludes n, so the length loop stops at n - 1. j to hi includes hi, which is required because the new element can add exactly hi - j inversions. If hi were below j the range would be empty, but hi is never below j when j is at most k.
Iterating over a range is cheap. for (j1 <- j to hi) doesn't build a list of numbers. The range is a small object that the loop walks through.
val hi inside the loop is created fresh in every pass, which is fine: it is never reassigned.

Complexity

Time: O(n^2 * k). The three loops run about n, k and at most n times. With the limits of 12 and 66 that is a few thousand steps.

Space: O(n * k). The table is the only extra memory.

Edge cases and common mistakes

No inversions. countPermutations(3, 0) returns 1: only the sorted permutation.
The maximum. countPermutations(3, 3) returns 1, the reversed permutation, and countPermutations(12, 66) returns 1 as well.
Forgetting the cap at k. Without math.min, the inner loop would write to column j + i, which can be past the last column. The method throws an ArrayIndexOutOfBoundsException.
n = 0. The table has a single row, so dp(1)(0) = 1 throws an ArrayIndexOutOfBoundsException. The notes don't promise an n below 1, so this is outside the lesson's inputs, but a robust version would return early.
Starting the length loop at 2. Row 1 holds the base case, and pass i = 1 is what builds row 2. Starting later leaves rows empty.
Overflow. No cell can exceed n!, so the largest value is below 479,001,600 and fits in an Int, which tops out near 2.1 billion. For larger n the cells would need to be Long.

Testing

n = 4, k = 2 gives 5.
n = 3, k = 1 gives 2.
n = 3, k = 0 gives 1.
n = 3, k = 3 gives 1.
n = 12, k = 30 gives 23697232.

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

Start learning free