Teaching Kids Programming – Dynamic Programming Algorithms to Compute the Number of Derangement Permutations

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given N numbers, we know the total number of permutation is N! (factorial). If every number is not in its original place i.e. 1 in first, 2 in second…, this is a derangement. Find out the number of Derangement Permutations given N numbers.

Bruteforcing may work, but takes time. There are N! permutations, and checking each one takes O(N) time to see if it is derangement. Thus the overall complexity is O(N!*N).

Top Down Dynamic Programming Algorithm to Compute the Number of Derangement Permutations

Let’s take a look at the N-th number. We surely can’t place it at last. We have N-1 places to choose from. If we choose K, we can swap K to the last number – which is F(N-2). Otherwise, there will be N-1 numbers to derangement permutated which is F(N-1).

Thus: the Dynamic Programming Transistion Equation/Function for N Derangement Permutation is:

We can implement this DP equation by Recursion with Memoization via the @lru_cache(None) or simply the @cache.

1
2
3
4
5
6
7
8
9

from functools import lru_cache
 
@lru_cache(None)
def f(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return (n - 1) * (f(n - 1) + f(n - 2))

from functools import lru_cache

@lru_cache(None)
def f(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return (n - 1) * (f(n - 1) + f(n - 2))

The time complexity is O(N) as each F(N) will be calculated once – they will be cached and reused if necessary. The space complexity is O(N) as we are using the cache.

This is Top Down Dynamic Programming as we are calculating Top Down i.e. F(N) then F(N-1) then F(N-2) … until we know the base cases F(1) and F(2).

Bottom-up Dynamic Programming Algorithm to Compute the Number of Derangement Permutations

Similar to Fibonacci Numbers, we can compute the F(1), F(2), F(3) until F(N), this is bottom up approach. We can use an array to save the values

1
2
3
4
5
6
7
8
9
10

def f(n):
    if n == 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]

def f(n):
    if n == 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]

The time and space complexity is O(N). However, as we only need F(N-1) and F(N-2) when we calculate F(N), thus we can simply use two variables to iteratedly updating.

1
2
3
4
5
6
7
8
9

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

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

The time complexity is O(N) and the space complexity is O(1) constant.

Derangement Algorithms

• Teaching Kids Programming – Dynamic Programming Algorithms to Compute the Number of Derangement Permutations
• Derangement Permutation Implementation using R Programming
• Teaching Kids Programming – (!3+3)*!3=10 – Derangement Algorithms via Dynamic Programming Algorithm

–EOF (The Ultimate Computing & Technology Blog) —