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