Start learning free

LESSON 313 OF 338 · DYNAMIC PROGRAMMING

Permutations With K Inversions in Go: Dynamic Programming by Insertion

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
    Ctrl + Enter to check

    GO · DYNAMIC PROGRAMMING

    Permutations With K Inversions in Go, explained

    Problem overview

    The method countPermutations(n, k) returns how many permutations of length 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. The sorted permutation has none; the fully reversed one has the most, n * (n - 1) / 2.

    For n = 4 and k = 2 the answer is 5. For example, [1, 3, 4, 2] has the inversions (3, 2) and (4, 2), while [3, 1, 2, 4] has (3, 1) and (3, 2). The notes keep n at 12 or less, but there are already 479,001,600 permutations of length 12, so checking each one is not the way.

    Approach: insert the largest element

    Build permutations of length i + 1 from permutations of length i. Take any permutation of the values 1 to i and insert the new value i + 1, the largest so far, in one of the i + 1 possible slots. Every permutation of length i + 1 arises from exactly one shorter permutation and one slot (remove the largest element to go back), so counting this way misses nothing and counts nothing twice.

    The largest element is greater than everything, so it forms an inversion with every element that stands after it and none with the elements before it. Put it last and it adds 0 inversions; put it one slot further left and it adds 1; put it first and it adds i. So one permutation with j inversions turns into i + 1 permutations of the longer length, with j, j + 1, ..., j + i inversions, one each.

    That gives the table. Let dp[i][j] be the number of permutations of length i with exactly j inversions. Each value dp[i][j] is added to dp[i+1][j1] for every j1 from j to j + i. Counts above k are never needed, so the range stops at k. For n = 4 and k = 2 the rows are:

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

    Columns are the inversion counts 0, 1 and 2. Length 3 has two permutations with one inversion ([2, 1, 3] and [1, 3, 2]) and two with two ([2, 3, 1] and [3, 1, 2]). The last row ends in 5, the answer.

    Step by step

    1. Allocate the table. make([][]int, n+1) creates n + 1 slots that are still nil slices. A range loop then gives each row its own make([]int, k+1), zero-filled.
    2. Seed length 1. A single element has no pairs, so dp[1][0] = 1.
    3. Loop over lengths. With i from 1 to n - 1, each pass builds row i + 1 from row i, so the last pass fills row n.
    4. Loop over inversion counts j from 0 to k: the source states.
    5. Loop over the targets. j1 runs from j to min(j+i, k). The built-in min (Go 1.21 and later) caps the range at k.
    6. Add the count. Each of the dp[i][j] permutations produces exactly one longer permutation for each j1, so dp[i+1][j1] += dp[i][j].
    7. Return dp[n][k].

    The solution in Go

    type Solution struct{}

func (s Solution) countPermutations(n int, k int) int {
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, k+1)
	}
	dp[1][0] = 1
	for i := 1; i < n; i++ {
		for j := 0; j <= k; j++ {
			for j1 := j; j1 <= min(j+i, k); j1++ {
				dp[i+1][j1] += dp[i][j]
			}
		}
	}
	return dp[n][k]
}

    Go details worth a closer look:

    • Methods on a struct. Go has no classes. Solution is an empty struct and countPermutations is a method with the receiver (s Solution). The receiver isn't used inside, which is allowed; only unused local variables and imports are compile errors.
    • A slice of slices is not a grid. make([][]int, n+1) allocates only the outer slice. Its elements are nil slices, and indexing a nil slice panics, which is why each row needs its own make.
    • for i := range dp with one variable yields indices. Assigning to dp[i] changes the outer slice, which is what we want; a copy of the element would not.
    • The loop condition is re-evaluated on every iteration, so min(j+i, k) is computed again each time. It is cheap and its value doesn't change inside the loop.
    • Zero values. The unwritten cells of make([]int, k+1) are 0, which is the right count for "no such permutation".

    Complexity

    The three loops run about n, k and up to n times, so the time is O(n * n * k). With n = 12 and k at most 66 that is under ten thousand operations. The table needs O(n * k) space. Counts fit easily in Go's 64-bit int: even the total number of permutations of length 12 is under 500 million.

    Edge cases and common mistakes

    • k = 0. Only the sorted permutation qualifies, so the answer is 1. For n = 3, countPermutations(3, 0) is 1.
    • k too large. For n = 3 the maximum is 3 inversions, so countPermutations(3, 3) is 1 (the reversed permutation) and countPermutations(3, 4) is 0. The table holds the zero without any special case.
    • n = 1. The loop doesn't run and the answer is dp[1][k]: 1 for k = 0, otherwise 0.
    • n = 0. The table has only row 0, so the line dp[1][0] = 1 stops the program with an index-out-of-range panic. The problem's inputs start at length 1, but a defensive version would return early.
    • Forgetting the cap at k. Without min(j+i, k), the target index would pass the end of the row and panic.
    • Overwriting with =. Several source cells feed the same target, so the update has to accumulate with +=.

    Testing

    Useful inputs: (4, 2) gives 5, and (3, 1) gives 2. The counts for all inversion numbers of length 4 are symmetric: 1, 3, 5, 6, 5, 3, 1 for k from 0 to 6, because reversing a permutation turns k inversions into 6 - k.

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