LESSON 347 OF 415 · DYNAMIC PROGRAMMING

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

SWIFT · DYNAMIC PROGRAMMING

Permutations With K Inversions in Swift, explained

Problem overview

The method countPermutations(_ n: Int, _ k: Int) returns how many permutations of length n have exactly k inversions. A permutation uses each of the numbers 1 to n exactly once. An inversion is a pair of positions i < j where the earlier value is larger: p(i) > p(j).

For n = 4 and k = 2 the answer is 5. For instance [1, 3, 4, 2] has two inversions, (3, 2) and (4, 2). The notes give N <= 12 and K <= N * (N - 1) / 2, which is the largest possible number of inversions, reached by the fully reversed permutation.

Approach: insert the largest element

Trying all n! permutations is too slow even for n = 12, which has about 479 million. Instead, build permutations one size at a time.

Take a permutation of the numbers 1 to i and insert the new largest number, i + 1, into one of i + 1 slots. The new number is larger than everything already there, so it forms an inversion with every element that ends up to its right, and with nothing to its left. Putting it at the very end adds 0 inversions, one slot further left adds 1, and so on, up to i new inversions at the very front.

That gives a clean rule. Each permutation of length i with j inversions produces exactly one permutation of length i + 1 for each of the new inversion counts j, j + 1, ..., j + i. Different slots give different permutations, and every permutation of length i + 1 arises from exactly one smaller permutation (remove the largest element), so nothing is counted twice or missed.

The counts for small sizes show the pattern. Each row lists the counts for j = 0, 1, 2, ...:

n=1: 1
n=2: 1 1
n=3: 1 2 2 1
n=4: 1 3 5 6 5 3 1

The entry for n = 4, j = 2 is 5, matching the example.

One row, worked out

Build row 3 from row 2 with k = 3. Row 2 is [1, 1, 0, 0]: the permutations [1, 2] (no inversions) and [2, 1] (one). Here i = 2, so inserting the 3 adds 0, 1 or 2 inversions.

dp[2][0] = 1 adds 1 to columns 0, 1 and 2 of row 3. These are [1, 2, 3], [1, 3, 2] and [3, 1, 2].
dp[2][1] = 1 adds 1 to columns 1, 2 and 3. These are [2, 1, 3], [2, 3, 1] and [3, 2, 1].

Row 3 is [1, 2, 2, 1], matching the table above. The cap matters when k is small: with k = 1 the second bullet would add to columns 1 only, and the targets 2 and 3 are never written.

Step by step

Create the table as a var with n + 1 rows of k + 1 zeros. dp[i][j] counts permutations of length i with j inversions.
Set dp[1][0] = 1. The only permutation of length 1 has no inversions.
Loop i over 1..<n. Each pass builds row i + 1 from row i, so the last pass (i = n - 1) builds row n.
Loop j over 0...k: every inversion count that row i can hold.
Find the highest count worth reaching. Inserting adds up to i inversions, so the targets run up to j + i. Counts above k can never matter for the answer, and the table has no columns for them, so the bound is hi = min(j + i, k).
Loop j1 over j...hi and add dp[i][j] to dp[i + 1][j1]. Each insertion slot gives one permutation, so the counts are simply added.
Return dp[n][k].

The solution in Swift

class Solution {
    func countPermutations(_ n: Int, _ k: Int) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: k + 1), count: n + 1)
        dp[1][0] = 1
        for i in 1..<n {
            for j in 0...k {
                let hi = min(j + i, k)
                for j1 in j...hi {
                    dp[i + 1][j1] += dp[i][j]
                }
            }
        }
        return dp[n][k]
    }
}

Swift details worth knowing:

Inferred types. Array(repeating: Array(repeating: 0, count: k + 1), count: n + 1) has no annotation, and Swift infers [[Int]] from the literal 0. Because arrays are value types, every row is its own copy.
Safe ranges. j...hi requires j <= hi. Here j <= k and j <= j + i, so hi is never below j. A closed range with its bounds reversed would stop the program with a run-time error, so the min cap is also what keeps the range valid.
1..<n with n = 1. The range is empty, so the loop is skipped and the method returns dp[1][k]. For n = 0, dp has a single row, so dp[1][0] = 1 goes out of bounds and the program crashes.
Global min. min(j + i, k) is Swift's global function and returns the smaller of its arguments.

Complexity

Time: O(n * k * n), that is O(n^2 * k). The loops run over i (up to n), over j (up to k), and over at most i + 1 values of j1. For n = 12 and k = 66 that is only a few thousand steps.

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

Edge cases and common mistakes

k = 0. Only the sorted permutation has no inversions, so the answer is 1 for every n.
Maximum k. With k = n * (n - 1) / 2 only the reversed permutation qualifies. For n = 3 and k = 3 the answer is 1.
Symmetry. The counts in each row read the same forwards and backwards, as the rows above show, because reversing a permutation turns inversions into non-inversions.
Using j + i without the cap. The inner loop would write past column k and crash.
Counting only i slots. A permutation of length i has i + 1 insertion slots, giving i + 1 different inversion counts from j to j + i. Stopping at j + i - 1 loses the permutations where the new element goes in front.

Testing

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

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

Start learning free