Count number of derangements (Tabulation)

Given a number n, find number of derangements in a set of n elements. A Derangement is a permutation with no element appears in its original position. For example, a derangement of [0, 1, 2] is [2, 0, 1].

Hint

Building upon understanding of Count number of derangements (Memoization). Tabulation essentially reconstructs the cache.

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

Python
Javascript

# Python implementation

def placement(n):
  cache = {}

  cache[1] = 0
  cache[2] = 1

  for i in range(3, n + 1):
    cache[i] = (i - 1) * (cache[i - 1] + cache[i - 2])

  return cache[n]

n = 4

print(placement(n))

// Javascript implementation

function placement(n) {
  const cache = []

  cache[1] = 0;
  cache[2] = 1;

  for (let i = 3; i < n + 1; i++) {
    cache[i] = (i - 1) * (cache[i - 1] + cache[i - 2]);
  }

  return cache[n];
}

const n = 4;

console.log(placement(n));