Coding Week 13 - Dynamic Programming

Question 1

Problem 1) Find The Derangement of An Array

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position.
You are given an integer n. There is originally an array consisting of n integers from 1 to n in ascending order, return the number of derangements it can generate.

Example 1:
Input: n = 3
Output: 2
Explanation: The original array is [1,2,3]. The two derangements are [2,3,1] and [3,1,2].

Question 1) What is the recursive formula for this problem:

A) f(n) = f(n - 1) * f(n - 2)
B) f(n) = (n - 1) * [f(n - 1) + f(n - 2)]
C) f(n) = (n - 1) * [f(n - 1) * f(n - 2)]
D) f(n) = (n - 1) * (n - 2) * [f(n - 1) + f(n - 2)]

Answer 1

B) f(n) = (n - 1) * [f(n - 1) + f(n - 2)]

In order to find the number of derangements for n numbers, firstly we can consider the original array to be [1,2,3,…,n]. Now, in order to generate the derangements of this array, assume that firstly, we move the number 1 from its original position and place it at the place of the number i. But, now, this ith position can be chosen in n−1 ways. Now, for placing the number i we have got two options:

We place i at the place of 1. By doing this, the problem of finding the derangements reduces to finding the derangements of the remaining n - 2 numbers, since we have got n - 2 numbers and n - 2 places, such that every number can’t be placed at exactly one position.

We don’t place i at the place of 1. By doing this, the problem of finding the derangements reduces to finding the derangements for the n - 1 elements(except 1). This is because, now we’ve got n - 1 elements and these n - 1 elements can’t be be placed at exactly one location(with i not being placed at the first position).

Based, on the above discussion, if f(n) represents the number of derangements of n elements, it can be obtained as:
f(n) = (n - 1) * [f(n - 1) + f(n - 2)]