Count Derangements (Permutation such that no element appears in its original position)
Last Updated :
22 Nov, 2024
A Derangement is a permutation of n elements, such that no element appears in its original position. For example, a derangement of [0, 1, 2, 3] is [2, 3, 1, 0].
Given a number n, find the total number of Derangements of a set of n elements.
Examples :
Input: n = 2
Output: 1
Explanation: For two balls [1, 2], there is only one possible derangement [2, 1].
Input: n = 3
Output: 2
Explanation: For three balls [1, 2, 3], there are two possible derangements [3, 1, 2] and [2, 3, 1].
Using Recursion – O(2 ^ n) Time and O(n) Space
The idea is to use recursion as, there are n – 1 way for element 0 (this explains multiplication with n – 1).
Let 0 be placed at index i. There are now two possibilities, depending on whether or not element i is placed at 0 in return.
- i is placed at 0: This case is equivalent to solving the problem for n-2 elements as two elements have just swapped their positions.
- i is not placed at 0: This case is equivalent to solving the problem for n-1 elements as now there are n-1 elements, n-1 positions and every element has n-2 choices
The formula used in the solution is:
F(n) = (n – 1) * (F(n – 1) + F(n – 2)
C++
// A Naive Recursive C++ program
// to count derangements
#include <bits/stdc++.h>
using namespace std;
int disarrange(int n) {
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (disarrange(n - 1) + disarrange(n - 2));
}
int main() {
int n = 4;
cout << disarrange(n);
return 0;
}
// A Naive Recursive java
// program to count derangements
import java.io.*;
class GfG {
// Function to count
// derangements
static int disarrange(int n) {
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (disarrange(n - 1) +
disarrange(n - 2));
}
public static void main (String[] args) {
int n = 4;
System.out.println(disarrange(n));
}
}
# A Naive Recursive Python3
# program to count derangements
def disarrange(n):
# Base cases
if (n == 1): return 0
if (n == 2): return 1
# countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (disarrange(n - 1) +
disarrange(n - 2))
n = 4
print(disarrange(n))
// A Naive Recursive C#
// program to count derangements
using System;
class GfG {
// Function to count
// derangements
static int disarrange(int n) {
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return (n - 1) * (disarrange(n - 1) +
disarrange(n - 2));
}
static void Main () {
int n = 4;
Console.Write(disarrange(n));
}
}
// A Naive Recursive Javascript
// program to count derangements
// Function to calculate derangements
function disarrange(n) {
// Base cases
if (n === 1) return 0;
if (n === 2) return 1;
// Recurrence relation: disarrange(n) = (n-1) * (disarrange(n-1) + disarrange(n-2))
return (n - 1) * (disarrange(n - 1) + disarrange(n - 2));
}
const n = 4;
console.log(disarrange(n));
Using Top-Down DP (Memoization) – O(n) Time and O(n) Space
Above recursive solution has properties that make it suitable for optimization using Dynamic Programming:
1. Optimal Substructure: The recursive relation demonstrates that the solution for F(n) can be constructed using the solutions to smaller subproblems, specifically F(n – 1) and F(n – 2).
2. Overlapping Subproblems: The function disarrange(n) recursively calls itself with n – 1 and n – 2. However, these subproblems are not independent. For example, when calculating disarrange(4), it will internally compute disarrange(3) and disarrange(2). Then, disarrange(3) will again compute disarrange(2), leading to redundant calculations.
C++
// A Dynamic programming based C++
// program to count derangements
#include <bits/stdc++.h>
using namespace std;
int calculate(int n, vector<int> &memo) {
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// If the value of n is previously
// calculated then return it here
if(memo[n] != -1) return memo[n];
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return memo[n] = (n - 1) * (calculate(n - 1, memo)
+ calculate(n - 2, memo));
}
int disarrange(int n) {
vector<int> memo(n + 1, -1);
return calculate(n, memo);
}
int main() {
int n = 4;
cout << disarrange(n);
return 0;
}
// A Dynamic programming based Java program
// to count derangements
import java.util.*;
class GfG {
static int calculate(int n, int[] memo) {
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// If the value of n is previously calculated
// then return it here
if (memo[n] != -1) return memo[n];
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
return memo[n] = (n - 1) * (calculate(n - 1, memo)
+ calculate(n - 2, memo));
}
static int disarrange(int n) {
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return calculate(n, memo);
}
public static void main(String[] args) {
int n = 4;
System.out.println(disarrange(n));
}
}
# A Dynamic programming based Python
# program to count derangements
def calculate(n, memo):
# Base cases
if n == 1:
return 0
if n == 2:
return 1
# If the value of n is previously
# calculated then return it here
if memo[n] != -1:
return memo[n]
# countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
memo[n] = (n - 1) * (calculate(n - 1, memo) + calculate(n - 2, memo))
return memo[n]
def disarrange(n):
memo = [-1] * (n + 1)
return calculate(n, memo)
n = 4
print(disarrange(n))
// A Dynamic programming based C#
// program to count derangements
using System;
class GfG {
static int Calculate(int n, int[] memo) {
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// If the value of n is previously
// calculated then return it here
if (memo[n] != -1) return memo[n];
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
memo[n] = (n - 1) * (Calculate(n - 1, memo) + Calculate(n - 2, memo));
return memo[n];
}
static int Disarrange(int n) {
int[] memo = new int[n + 1];
Array.Fill(memo, -1);
return Calculate(n, memo);
}
static void Main() {
int n = 4;
Console.WriteLine(Disarrange(n));
}
}
// A Dynamic programming based
// JavaScript program to count derangements
function calculate(n, memo) {
// Base cases
if (n === 1) return 0;
if (n === 2) return 1;
// If the value of n is previously
// calculated then return it here
if (memo[n] !== -1) return memo[n];
// countDer(n) = (n-1)[countDer(n-1) + der(n-2)]
memo[n] = (n - 1) * (calculate(n - 1, memo) + calculate(n - 2, memo));
return memo[n];
}
function disarrange(n) {
let memo = Array(n + 1).fill(-1);
return calculate(n, memo);
}
const n = 4;
console.log(disarrange(n));
Using Bottom-Up DP (Tabulation) – O(n) Time and O(n) Space
The approach is similar to the previous one. just instead of breaking down the problem recursively, we iteratively build up the solution by calculating in bottom-up manner. Maintain a dp[] table such that dp[i] stores the Count Derangements for i.
Base Case:
- For i = 1 dp[i] = 0
- for i = 2 dp[i] = 1
Recursive Case:
- For i > 2 dp[i] = (i – 1) * (dp[i-1] + dp[i – 1])
C++
// Optimized DP-based solution to
// count derangements
#include <bits/stdc++.h>
using namespace std;
int disarrange(int n) {
// Create a DP array to store
// results
vector<int> dp(n + 1);
// Base cases
dp[1] = 0;
dp[2] = 1;
// Fill the DP array using the recursive relation
for (int i = 3; i <= n; i++) {
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
}
return dp[n];
}
int main() {
int n = 4;
cout << disarrange(n);
return 0;
}
// Optimized DP-based solution to
// count derangements
import java.util.*;
class GfG {
static int disarrange(int n) {
// Create a DP array to store results
int[] dp = new int[n + 1];
// Base cases
dp[1] = 0;
dp[2] = 1;
// Fill the DP array using the recursive relation
for (int i = 3; i <= n; i++) {
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
}
return dp[n];
}
public static void main(String[] args) {
int n = 4;
System.out.println(disarrange(n));
}
}
# Optimized DP-based solution
# to count derangements
def disarrange(n):
# Create a DP array to store results
dp = [0] * (n + 1)
# Base cases
dp[1] = 0
dp[2] = 1
# Fill the DP array using the
# recursive relation
for i in range(3, n + 1):
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
return dp[n]
n = 4
print(disarrange(n))
// Optimized DP-based solution to count derangements
using System;
class GfG {
static int Disarrange(int n) {
// Create a DP array to store results
int[] dp = new int[n + 1];
// Base cases
dp[1] = 0;
dp[2] = 1;
// Fill the DP array using the recursive relation
for (int i = 3; i <= n; i++) {
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
}
return dp[n];
}
static void Main() {
int n = 4;
Console.WriteLine(Disarrange(n));
}
}
// Optimized DP-based solution to count derangements
function disarrange(n) {
// Create a DP array to store results
const dp = new Array(n + 1).fill(0);
// Base cases
dp[1] = 0;
dp[2] = 1;
// Fill the DP array using the recursive relation
for (let i = 3; i <= n; i++) {
dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]);
}
return dp[n];
}
const n = 4;
console.log(disarrange(n));
Using Space Optimized DP – O(n) Time and O(1) Space
To optimize the space complexity to O(1) we can avoid using an array and instead use two variables to store the previous two results, as we only need the last two values to compute the next value. This will reduce the space requirement significantly.
C++
// Optimized DP-based solution to count
// derangements with O(1) space
#include <bits/stdc++.h>
using namespace std;
int disarrange(int n) {
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// Variables to store previous two results
// Equivalent to dp[1]
int prev2 = 0;
// Equivalent to dp[2]
int prev1 = 1;
// Calculate derangements using the optimized
// space approach
for (int i = 3; i <= n; i++) {
int curr = (i - 1) * (prev1 + prev2);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
int main() {
int n = 4;
cout << disarrange(n);
return 0;
}
// Optimized DP-based solution to count
// derangements with O(1) space
class GfG {
static int disarrange(int n) {
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// Variables to store previous two results
// Equivalent to dp[1]
int prev2 = 0;
// Equivalent to dp[2]
int prev1 = 1;
// Calculate derangements using the
// optimized space approach
for (int i = 3; i <= n; i++) {
int curr = (i - 1) * (prev1 + prev2);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
public static void main(String[] args) {
int n = 4;
System.out.println(disarrange(n));
}
}
# Optimized DP-based solution to count
# derangements with O(1) space
def disarrange(n):
# Base cases
if n == 1:
return 0
if n == 2:
return 1
# Variables to store previous two results
# Equivalent to dp[1]
prev2 = 0
# Equivalent to dp[2]
prev1 = 1
# Calculate derangements using the
# optimized space approach
for i in range(3, n + 1):
curr = (i - 1) * (prev1 + prev2)
prev2 = prev1
prev1 = curr
return prev1
n = 4
print(disarrange(n))
// Optimized DP-based solution to count
// derangements with O(1) space
using System;
class GfG {
static int Disarrange(int n) {
// Base cases
if (n == 1) return 0;
if (n == 2) return 1;
// Variables to store previous two results
// Equivalent to dp[1]
int prev2 = 0;
// Equivalent to dp[2]
int prev1 = 1;
// Calculate derangements using the optimized
// space approach
for (int i = 3; i <= n; i++) {
int curr = (i - 1) * (prev1 + prev2);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
static void Main() {
int n = 4;
Console.WriteLine(Disarrange(n));
}
}
// Optimized DP-based solution to count
// derangements with O(1) space
function disarrange(n) {
// Base cases
if (n === 1) return 0;
if (n === 2) return 1;
// Variables to store previous two results
// Equivalent to dp[1]
let prev2 = 0;
// Equivalent to dp[2]
let prev1 = 1;
// Calculate derangements using the
// optimized space approach
for (let i = 3; i <= n; i++) {
let curr = (i - 1) * (prev1 + prev2);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
const n = 4;
console.log(disarrange(n));