Teaching Kids Programming – How Many Games are Played in World Cup (Combinatorics and Permutations) | ninjasquad

**Teaching Kids Programming**: Videos on **Data Structures and Algorithms**

### How Many Matches are played during Worldcup?

There are 32 teams, allocated to 8 Groups of Four. In The Group Stages, there are 6 matches each which is .

Half of 32 = 16 qualifies (top 2 in the groups) to knock-out stages. Each knock-out elinimates one team, so 15 matches = 15 teams elinimated. Plus, there is one more match between third and fourth place.

Therefore: 8×6+15+1 = 64 matches.

Next worldcup has 48 teams – and thus total matches played 12×6+23+1=96. 12=groups,6=matches played in group stages. 23=knock-out, 1=3 vs 4.

### Combinatorics

Choosing M out of N times (the order does not matter) can be noted as

Picking 0 out of N is 1 aka

Picking N out of N is 1 aka

Picking M out of N when M is greater than N is 0 aka when where we want to pick M items out of N:

For the first item, we can pick or skip.

When pick, we have M-1 items to pick from N-1 items.

When skip, we have M items to pick from N-1 items.

Thus:

We can implement this via Recursion with Memoization aka Top Down Dynamic Programming:

1 2 3 4 5 6 7 8 |
from collections import * @cache # or @lru_cache(maxsize=None) def C(N, M): if M == N or M == 0: return 1 if M > N: return 0 return C(N-1, M) + C(N-1, M-1) |

from collections import * @cache # or @lru_cache(maxsize=None) def C(N, M): if M == N or M == 0: return 1 if M > N: return 0 return C(N-1, M) + C(N-1, M-1)

This is basically solving the Pascal triangle where each number is the sum of two numbers on the shoulder, the border numbers are all ones. We can also solve this via Iterative/Loop – where we use arrays (space can be optimised to one dimension) to store the previous Combination Numbers.

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1

The Combination Number can also be computed via the following equation:

In Python, we can compute the combination number using the **comb** function (N, M) in the math library/package:

1 2 3 |
from math import comb print(comb(4, 2)) # prints 6 |

from math import comb print(comb(4, 2)) # prints 6

We can use the combinations from the itertools to obtain the **combinations** aka the function has the signature: combinations(iterator, number to pick)

1 2 3 4 |
from itertools import combinations print(list(combinations((1,2,3), 2))) # [(1, 2), (1, 3), (2, 3)] |

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

### Permutations

For permutations, the order of the items matters, for example, (1, 2) is different than (2, 1). We can take permutations as P(N, M) which is equal to C(N, M) and do full permutations on M items aka P(M, M)

Full permutations of N items is N factorial. The first item we have N choices, the second item we have N-1 choices and so on, the last item we have 1 choices.

Thus:

In Python, we can compute the permutations number using the **perm** function (N, M) in the math library/package:

1 2 3 |
from math import perm print(perm(4, 2)) # prints 12 |

from math import perm print(perm(4, 2)) # prints 12

We can use the permutations from the itertools to obtain the **permutations** aka the function has the signature: permutations(iterator, number to pick)

1 2 3 4 |
from itertools import permutations print(list(permutations((1,2,3), 2))) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] |

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

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

1146 words

**Last Post**: Teaching Kids Programming – Algorithms to Check a Circular Sentence

Source: Internet