Teaching Kids Programming – Three Algorithms to Compute the Combination Number

Teaching Kids Programming: Videos on Data Structures and Algorithms

In Mathematics (Combinatorial Mathematics), the combinations denote the number of ways to pick M items out of N items aka , and the sequences/orders do not matter. For example, there are 3 ways to pick two out of three:

[1,2], [1,3], [2,3]

And it is not difficult to find that:

The formula:

And the permutation (when sequence matters), can be computed by first picking the numbers (via Combination) and then perform a full permutation on the M items – which is N! aka i.e. there are N choices for picking the first number, and N-1 choices the next, N-2 .. and so on (the last slot has only 1 choice).

Consider there are N items, and we need to pick M items. For the next item, we have two choices, pick or skip:

WHen we skip it, we have to pick M items out of N-1 items.
When we pick it, we have to pick M-1 items out of N-1 items.

Thus .

The boundary conditions:

and if M is larger than N.

Combination and Permutation Functions in Python

In Python, we have the following two functions (comb and perm) in math library that computes the combinations and permuations respectively:

1
2
3
4

from math import comb, perm
 
comb(3, 2) # 3
perm(3, 2) # 6

from math import comb, perm

comb(3, 2) # 3
perm(3, 2) # 6

We also have two similar functions in itertools package, however, they are returning the iterator to combinations and permuations respectively:

1
2
3
4
5
6

from itertools import combinations, permutations
 
list(combinations((1,2,3),2))
# [(1, 2), (1, 3), (2, 3)]
list(permutations((1,2,3),2))
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

from itertools import combinations, permutations

list(combinations((1,2,3),2))
# [(1, 2), (1, 3), (2, 3)]
list(permutations((1,2,3),2))
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

We can use the Recursive algorithm to obtain the combinations and permutations.

Compute Combination via Top Down Dynamic Programming Algorithm + Recursion with Memoization

Since we have the recurrence relation of the combination, we can implement it (simply translating the formula) via Recursion. And by using the magic keyword @cache (from lru_cache, LRU) to store the intermediate values, we are actually turning it into Top Down Dynamic Programming:

1
2
3
4
5
6
7

@cache
def comb(n, r):
    if n < r:
        return 0
    if n == r or r == 0:
        return 1
    return comb(n - 1, r) + comb(n - 1, r - 1)

@cache
def comb(n, r):
    if n < r:
        return 0
    if n == r or r == 0:
        return 1
    return comb(n - 1, r) + comb(n - 1, r - 1)

There are states and therefore the time/space complexity is . Using Recursion with Memoization simplifies the implementation, as we do not care about the details e.g. where to store the seen values.

Compute Combination via Bottom Up Dynamic Programming Algorithm

Alternatively, we can manually store those intermediate values in an array, aka Bottom Up Dynamic Programming. The Bottom Up approach is non-trivial and hard to get it right because of boundary checks.

We need to initialize the boundary values to 1. And then start filling the Pascal Triangle Top Bottom.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def comb(n, r):
    if n < r:
        return 0
    if n == r or r == 0:
        return 1
    a = [[0] * (r+1) for _ in range(n+1)]
    for i in range(n + 1):
        a[i][0] = 1
    for i in range(r + 1):
        a[0][i] = a[i][i] = 1
    for i in range(1, n + 1):
        for j in range(1, min(i, r + 1)):
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1]
    return a[-1][-1]

def comb(n, r):
    if n < r:
        return 0
    if n == r or r == 0:
        return 1
    a = [[0] * (r+1) for _ in range(n+1)]
    for i in range(n + 1):
        a[i][0] = 1
    for i in range(r + 1):
        a[0][i] = a[i][i] = 1
    for i in range(1, n + 1):
        for j in range(1, min(i, r + 1)):
            a[i][j] = a[i - 1][j] + a[i - 1][j - 1]
    return a[-1][-1]

The advantage of Bottom Up is that it is usually practically faster because of no function calls despite of the same time/space complexity.

We notice that the C(N, X) value is only dependent on two C(N-1, Y), and thus we can compress the 2D space into one as we don’t need to store the values prior to C(N-1,Y).

To avoid values being overwritten, for the inner loop, we have to loop backwards:

1
2
3
4
5
6
7
8
9
10
11

def comb(n, r):
    if n < r:
        return 0
    if n == r or r == 0:
        return 1         
    a = [1] + [0] * (n)
    for i in range(n + 1):
        a[i] = 1
        for j in range(i - 1, 0, -1):
            a[j] += a[j - 1]
    return a[r]  

def comb(n, r):
    if n < r:
        return 0
    if n == r or r == 0:
        return 1         
    a = [1] + [0] * (n)
    for i in range(n + 1):
        a[i] = 1
        for j in range(i - 1, 0, -1):
            a[j] += a[j - 1]
    return a[r]  

Same time complexity e.g. , but the space complexity is improved to O(N). We could further improve to O(R) – but again we have to be extra careful that the array index should not be out of bounary:

1
2
3
4
5
6
7
8
9
10
11
12

def comb(n, r):
    if n < r:
        return 0
    if n == r or r == 0:
        return 1         
    a = [1] + [0] * (r)
    for i in range(n + 1):
        if i < r + 1: # checking bounary
            a[i] = 1
        for j in range(min(i - 1, r), 0, -1):
            a[j] += a[j - 1]
    return a[r]  

def comb(n, r):
    if n < r:
        return 0
    if n == r or r == 0:
        return 1         
    a = [1] + [0] * (r)
    for i in range(n + 1):
        if i < r + 1: # checking bounary
            a[i] = 1
        for j in range(min(i - 1, r), 0, -1):
            a[j] += a[j - 1]
    return a[r]  

Permutations and Combinations

• Using Bitmasking Algorithm to Compute the Combinations of an Array
• Teaching Kids Programming – Recursive Backtracking Algorithm to Compute the Combinations
• Teaching Kids Programming – Recursive Permutation Algorithm
• Teaching Kids Programming – Introduction to Permutation and Combination
• Teaching Kids Programming – Three Algorithms to Compute the Combination Number
• A Recursive Full Permutation Algorithm in Python
• The Permutation Iterator in Python
• GoLang: Full Permutation Command Line Tool
• The Permutation Algorithm for Arrays using Recursion
• Full Permutation Algorithm Implementation in BASH

–EOF (The Ultimate Computing & Technology Blog) —