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