Teaching Kids Programming – (!3+3)*!3=10 – Derangement Algorithms via Dynamic Programming Algorithm | ninjasquad

**Teaching Kids Programming**: Videos on **Data Structures and Algorithms**

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].Example 2:

Input: n = 2

Output: 1

### Derangement Algorithm via Recursion

Let’s use to denote the number of ways to put N items in such derangement order aka the i-th item cannot be put in index i. The base conditions are:

Now, let’s take a look at the item N. We cannot place it in the last position but we can put it at position 1 to N-1 so N-1 choices. If we put it at K where K is not N, then we have two choices for K, we can swap it with N thus or we don’t, thus

so further simplified to:

Thus, recursive algorithm similar to Fibonacci numbers which can be done in simple Recursion:

1 2 3 4 5 6 |
def f(n): if n in (0, 1): return 0 if n == 2: return 1 return (n - 1) * (f(n-1) + f(n-2)) |

def f(n): if n in (0, 1): return 0 if n == 2: return 1 return (n - 1) * (f(n-1) + f(n-2))

The time complexity is exponential since we re-calculate the intermediate f values.

### Derangement Algorithm via Dynamic Programming

We can simply add a @cache keyword or use a hash map aka dictionary to remember the values so that are not calculated over and over again. This is Top Down Dynamic Programming Algorithm aka Recursion with Memoization:

1 2 3 4 5 6 7 |
@cache def f(n): if n in (0, 1): return 0 if n == 2: return 1 return (n - 1) * (f(n-1) + f(n-2)) |

@cache def f(n): if n in (0, 1): return 0 if n == 2: return 1 return (n - 1) * (f(n-1) + f(n-2))

The Dynamic Programming algorithm can be done in Bottom Up manner. Below uses the Array to calculate and store the derangement values from a smaller N e.g. F(0), F(1), F(2) … F(N)

1 2 3 4 5 6 7 8 9 10 |
def f(n): if n in (0, 1): return 0 if n == 2: return 1 dp = [0] * (n + 1) dp[2] = 1 for i in range(3, n + 1): dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) return dp[-1] # or dp[n] |

def f(n): if n in (0, 1): return 0 if n == 2: return 1 dp = [0] * (n + 1) dp[2] = 1 for i in range(3, n + 1): dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) return dp[-1] # or dp[n]

The time/space complexity is O(N). The f(n) value is only dependent on f(n-1) and f(n-2) the previous two values, similar to Fibonacci Numbers, and thus we can use two variables to store these:

1 2 3 4 5 6 7 8 9 |
def f(n): if n in (0, 1): return 0 if n == 2: return 1 a, b = 0, 1 for i in range(3, n + 1): a, b = b, (a + b) * (i - 1) return b |

def f(n): if n in (0, 1): return 0 if n == 2: return 1 a, b = 0, 1 for i in range(3, n + 1): a, b = b, (a + b) * (i - 1) return b

### Derangement Algorithms

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

930 words

**Last Post**: Teaching Kids Programming – Count Unreachable Pairs of Nodes in an Undirected Graph (Union Find and Disjoint Set Algorithm) **Next Post**: Teaching Kids Programming – Recursive Depth First Search Algorithm to Evaluate the Boolean Binary Tree

Source: Internet