Teaching Kids Programming – Three Algorithms to Compute the Combination Number | ninjasquad

**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

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

1603 words

**Last Post**: Password Protect or IP Restriction on WordPress wp-admin Folder (htaccess and htpasswd) **Next Post**: Teaching Kids Programming – Number of Ways to Reach a Position After Exactly k Steps (Combinations + Math + Dynamic Programming Algorithms)

Source: Internet