Josephus permutation
Have you ever played a game of elimination where one person gets out in each round until there is only one person left? That's exactly what Josephus Permutation is.
Imagine that there are a group of soldiers standing in a circle, and they have to kill the person next to them every two soldiers until there is only one person (soldier) left standing. This is essentially the idea behind the Josephus Permutation problem.
Let's say that we have five soldiers standing in a circle: A, B, C, D, E, and we start killing every other soldier. First, we kill soldier B and move to the next person, which is C. We skip D and kill E. We start over again from A and kill C first this time, then we skip D and kill A. The last remaining soldier standing is D.
This is a pattern that can be generalized by a formula, where the soldiers are numbered from 1 to n, and each kth soldier is killed until there is only one left standing:
- In the first round, we start from the first soldier and kill every kth soldier until the end of the circle.
- We then start a new round from the next soldier who was skipped in the first round.
- We continue skipping k-1 soldiers and killing the kth one until the end of the circle.
- We keep repeating this process until there is only one soldier left standing.
This is the Josephus Permutation formula, which can be used to solve various problems related to this game of elimination.
Imagine that there are a group of soldiers standing in a circle, and they have to kill the person next to them every two soldiers until there is only one person (soldier) left standing. This is essentially the idea behind the Josephus Permutation problem.
Let's say that we have five soldiers standing in a circle: A, B, C, D, E, and we start killing every other soldier. First, we kill soldier B and move to the next person, which is C. We skip D and kill E. We start over again from A and kill C first this time, then we skip D and kill A. The last remaining soldier standing is D.
This is a pattern that can be generalized by a formula, where the soldiers are numbered from 1 to n, and each kth soldier is killed until there is only one left standing:
- In the first round, we start from the first soldier and kill every kth soldier until the end of the circle.
- We then start a new round from the next soldier who was skipped in the first round.
- We continue skipping k-1 soldiers and killing the kth one until the end of the circle.
- We keep repeating this process until there is only one soldier left standing.
This is the Josephus Permutation formula, which can be used to solve various problems related to this game of elimination.