Inversions - Memoization

Dynamic Programming, Optimization

Originally posted on Oct 18, 2014 in my previous blog.

Problem posted on SPOJ.com

In this problem we need to calculate the number of inversions. a contains numbers from 1 to n in a specific order. An inversion here is defined as a(i) > a(j) && i<=j in one permutation. So the problem reduces to finding those sequences over all permutations such that they have exactly k permutations. This can be done by brute force - listing out all permutations of numbers (from 1 to n) and counting those sequences which have exactly k inversions. Since listing all the permutations takes O(n!), this method would be computationally intensive for large values of n.

We can try a recursive approach for this problem. Note that if n = 0, number of permutations is 0, and if k = 0 number of permutations is 1. The recursion is shown below,

permut(n) = {
    0                                          if n == 0;
    1                                          if k == 0;
    sum(permut(n - 1, k - i)) (for 0 <= i < n) otherwise
}
                      

This recursion can be coupled with memoization to take care of redundant solving of subproblems. (NOTE: if there are many queries, it is better to follow a bottom-up approach rather than memoization. In this particular problem there are less than 10 queries). Initialize a 2d array dp[n][k] with -1.

permut(int n, int k) {
    // boundary cases
    if(n == 0)
        return 0;
    if(k == 0)
        return 1;

    if(dp[n][k] != -1)
        return dp[n][k];

    int sum = 0;
    for(int i = 0; i < n; i++) {
        sum += permut(n - 1, k - i);
    }

    return (dp[n][k] = sum);
}
                  

Happy Memoization!