Start learning free

LESSON 342 OF 410 · DYNAMIC PROGRAMMING

Permutations with K Inversions in Java: 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
    Ctrl + Enter to check

    JAVA · DYNAMIC PROGRAMMING

    Permutations With K Inversions in Java, explained

    Problem overview

    An inversion in a permutation p is a pair of positions (i, j) with i < j and p(i) > p(j): two numbers that are in the wrong order. The sorted permutation [1, 2, 3] has no inversions, and [3, 2, 1] has all three possible ones. The method countPermutations takes n and k and returns how many permutations of the numbers 1 to n have exactly k inversions. The lesson's notes limit n to 12 and k to the largest possible inversion count, n * (n - 1) / 2.

    For n = 4 and k = 2 the answer is 5, and the permutations are [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 4, 3] and [3, 1, 2, 4]. Check one: in [1, 4, 2, 3] the inverted pairs are (4, 2) and (4, 3), so there are exactly 2.

    Approach: build longer permutations from shorter ones

    Generating all n! permutations and counting inversions in each works for tiny n only: 12! is 479,001,600 permutations, each needing an inversion count. Dynamic programming avoids this by counting without listing.

    The key is to grow a permutation by inserting the largest number. Take any permutation of the numbers 1 to i and insert the new number i + 1 somewhere. The new number is bigger than everything else, so it forms an inversion with every element that ends up to its right, and with none to its left. Put it at the end: 0 new inversions. One place to the left: 1 new inversion. At the very front: i new inversions. So the i + 1 insertion positions add exactly 0, 1, 2, ..., i inversions, one position for each amount.

    That gives a recurrence. Let dp[i][j] be the number of permutations of length i with exactly j inversions. Every such permutation produces i + 1 longer ones, with j, j + 1, ..., j + i inversions. Different permutations or different positions never produce the same longer permutation, because removing the largest number recovers the original permutation and the position. The counts can therefore be added without worrying about double counting.

    Here is the table for n = 4 and k = 2, with columns for 0, 1 and 2 inversions:

    Length0 inversions1 inversion2 inversions
    1100
    2110
    3122
    4135

    The bottom-right cell is the answer, 5. Length 3 has 6 permutations in total, split 1, 2, 2 and 1 across 0 to 3 inversions. The column for 3 inversions is not shown, because the table stops at k = 2.

    Step by step

    1. Create the table. Declare dp as new int[n + 1][k + 1]: rows for lengths 0 to n and columns for 0 to k inversions. Java fills a new int array with zeros, so no initialisation loop is needed.
    2. Set the base case. dp[1][0] = 1. The only permutation of length 1 has no inversions.
    3. Loop over lengths. The index i runs from 1 to n - 1. Each pass builds row i + 1 from row i. The final pass fills row n.
    4. Loop over inversion counts. The index j runs from 0 to k and selects the cell dp[i][j] to push forward.
    5. Loop over the new inversion counts. The index j1 runs from j to Math.min(j + i, k). These are the inversion counts the extended permutations can have. Counts above k never contribute to the answer, so the range is capped at k.
    6. Add. dp[i + 1][j1] += dp[i][j]. Every permutation counted in dp[i][j] yields exactly one permutation of length i + 1 with j1 inversions.
    7. Return dp[n][k].

    The solution in Java

    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];
    }
}

    Java details worth noticing:

    • A two-dimensional array is an array of arrays. new int[n + 1][k + 1] allocates all the rows at once, and every cell starts at 0.
    • The loop bound is recomputed. Math.min(j + i, k) in the loop condition is evaluated on every pass of the innermost loop. That is cheap, and it keeps the cap in one place.
    • The pre-increment ++j1 behaves the same as j1++ in a loop header, because the value of the expression is not used.
    • int is large enough. A table entry never exceeds the number of permutations of its length, and with n up to 12 that is at most 12! = 479,001,600, which fits in an int (maximum 2,147,483,647). For much larger n the counts would overflow silently, and a long or a result modulo a prime would be needed.

    Complexity

    The three loops run about n times, k + 1 times and up to i + 1 times, so the time is O(n^2 * k). The table has (n + 1) * (k + 1) cells, so the space is O(n * k). Since only row i is read when row i + 1 is built, two rows would be enough to cut the memory to O(k). A prefix-sum version of the inner loop also reduces the time to O(n * k).

    Edge cases and common mistakes

    • k = 0. Exactly one permutation, the sorted one, has no inversions, so countPermutations(3, 0) is 1.
    • The maximum k. Only the reversed permutation reaches n * (n - 1) / 2 inversions. For n = 4 and k = 6 the result is 1.
    • k above the maximum. No permutation has that many inversions, and the method returns 0. For n = 4 and k = 7 the table simply stays zero in that cell.
    • n = 1. The loop does not run and the method returns dp[1][0], which is 1 for k = 0.
    • n = 0. The table has only one row, so dp[1][0] = 1 throws ArrayIndexOutOfBoundsException. The lesson's inputs start at length 1.
    • Stopping at the wrong row. The loop ends at i < n because each pass writes row i + 1. Looping to i <= n would write outside the table.

    Testing

    Try (4, 2) (5), (3, 1) (2), (3, 3) (1) and (5, 2) (9).

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