I have a number n and i want to find number of ways i can create an array having n distinct elements from 1 to n such that for no index i we have A[i] = i.

For example n = 4 we have 9 permutations
[ 2 1 4 3 ] ,[ 2 3 4 1 ],[ 2 4 1 3 ],[ 3 1 4 2 ],[ 3 4 1 2 ],[ 3 4 2 1 ],[ 4 1 2 3 ],[ 4 3 1 2 ],[ 4 3 2 1 ].

I know the brute force approach which will have time complexity O(n!). Is there any other optimized way of doing this? Something in O(n) or O(nlogn) complexity.

CodePudding user response：

A permutation of {1,2,...,n} in which no element occurs in its position is called a derangement. You are looking for the number of derangements of an n-element set, for which there is a formula (which can be obtained using the inclusion-exclusion principle). The formula is $n! \sum_{i=0}^n (-1)^i / i!$. See the Wikipedia article on derangements, which derives this formula.

In the limit, this value approaches n!/e, which is approximately 0.37 n!, i.e 37% of the n! permutations would be derangements.

CodePudding user response：

The Counting Derangements problem can be solved in linear time O(n) using dynamic programming, thanks to Euler who proved the recurrence relation :

!n = (n-1) * (!(n-1)   !(n-2))

This allows to solve the problem from bottom up instead of recursively, keeping track of the 2 preceding terms !(n-1) and !(n-2) (eg. in javascript) :

function a(n) {
  if (n < 3) {
    return n < 0 ? undefined : Math.abs(n-1);
  }

  // For n = 3, we got :
  let x = 1; // !(n-1)
  let y = 0; // !(n-2)

  for (let k=3; k<=n; k  ) {
    const fk = (k - 1) * (x   y);
    [x, y] = [fk, x];
  }

  return x;
}    

Euler also proved another recurrence relation :

!n = n * !(n-1)   (-1)^n

Using the same technique, there is only one preceding term (variable) to track. This translates to :

function a(n) {
  if (n < 3) {
    return n < 0 ? undefined : Math.abs(n-1);
  }

  let x = 1; // !(n-1) for n = 3

  for (let k=3; k<=n; k  ) {
    x = k*x   (-1)**k;
  }

  return x;
}