Find number of permutation with K inversions (Memoization)

Given two numbers n and k, find how many permutations of the first n number have exactly k inversion. An inversion is defined as a[i] > a[j] for i < j.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Find number of permutation with K inversions, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = None

def count(n, k):
  if n == 0: return 0
  if k == 0: return 1

  global cache
  if not cache:
    cache = [[None for _ in range(k + 1)] for _ in range(n + 1)]

  if not cache[n][k]:
    result = 0
    
    for i in range(min(k, n - 1) + 1):
      result += count(n - 1, k - i)
    
    cache[n][k] = result
  
  return cache[n][k]

n = 4
k = 2

print(count(n, k))

let cache = null;

function count(n, k) {
  if (n === 0) return 0;
  if (k === 0) return 1;
  
  if (!cache) {
    cache = Array.from(Array(n + 1), () => Array(k + 1).fill(null));
  }

  if (cache[n][k] == null) {
    let result = 0;
  
    for (let i = 0; i <= Math.min(k, n - 1); i++) {
      result += count(n - 1, k - i);
    }
    
    cache[n][k] = result;
  }

  return cache[n][k];
}

const n = 4;
const k = 2;

console.log(count(n, k));