Teaching Kids Programming – Introduction to Permutation and Combination

Teaching Kids Programming: Videos on Data Structures and Algorithms

Permutation and Combination are the math concepts to count. Given N items, if we want to choose M items (M no bigger than N) from it, there are C(N, M) ways if the order does not matter, or P(N, M) is the order matters.

Permutation

If there are N items, we have N choices for the first item, and N-1 for the second item and so on. Thus:

In particular:

Combination

For Combination, the order does not matter. So we can first count the P(N, M) and then divide by P(M, N).

In particular:

Choosing M items from N is the same as choosing N-M items from N:

Dynamic Programming to Compute the Combination

If we want to calculate C(N, M), for the last item, we can choose to pick or not pick. If we pick, we have C(N-1, M-1), if we don’t pick the last item, then we have C(N-1, M). Therefore:

To implement this in Python via Recursive Algorithm with Memoization aka Dynamic Programming Algorithm:

1
2
3
4
5
6
7
8

# caching the intermediate results
@lru_cache(None)
def C(N, M):
  if M == N or M == 0:
    return 1
  if M == 1:
    return N
  return C(N - 1, M - 1) + C(N - 1, M) 

# caching the intermediate results
@lru_cache(None)
def C(N, M):
  if M == N or M == 0:
    return 1
  if M == 1:
    return N
  return C(N - 1, M - 1) + C(N - 1, M) 

Pascal Triangle and Combination

Revisit the Pascal Triangle:

1 
1 1
1 2 1
1 3 3 1
1 4 6 4 1

We can see for the numbers in Pascal Triangle, we can see it equals to those two numbers above it – which perfectly maps to the Combination Formula.

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) —