# Teaching Kids Programming – Three Algorithms to Compute the Combination Number

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 $tex_6e99eb1b55e376d97dcfea934131fb93 Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$, 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:

$tex_8d5ca73fb16a30ed3a4361638727a316 Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$

The formula: $tex_f33a65a4bd1f46366a7f7ff7b8c9b2a3 Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$

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 $tex_40e67f21df57bd537a9add3be9baa40f Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$ 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).

$tex_4bae6e41b9aa84c13aee73d01c85f20c Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$

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 $tex_ffdf7d75e794b0634fd3e26af2818eae Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$.

The boundary conditions:

$tex_d0b80e49015d27423947574e4f159c00 Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$
and $tex_6968974bc5450970d9441d10a8d30b25 Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$ 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 $tex_b1e2bd35fc413bc8562864d78a56b850 Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$ states and therefore the time/space complexity is $tex_5d195bed42e540660ec1d295ecc6c73c Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$. 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. $tex_2f4930896c5cd511812eb5d596694f46 Teaching Kids Programming - Three Algorithms to Compute the Combination Number algorithms Combination Combinatoric Mathematics Dynamic Programming math Memoization Recursion teaching kids programming youtube video$, 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]  ```

GD Star Rating