An overview of the

Joseph ring problem, also known as Joseph murder problem or handkerchief loss problem, is a classical algorithm problem. There are many variations of the problem description, but the general idea is the same. This paper will solve Joseph’s ring problem in three ways: cyclic linked list, ordered array and mathematical recursion.

Problem description

So what is Joseph’s ring problem?

After the Roman occupation of Joe tower pat, 39 jews and Josephus and his friend hiding in a hole, 39 decided jews would rather die don’t was caught by the enemy, then made a suicide, 41 people arranged in a circle, start from 1 individual number off, each number off to third person would have to commit suicide, and then the next number off again, Until everyone committed suicide. Josephus and his friends, however, did not want to comply. Start with one person, pass k-2 people (since the first person has already been passed), and kill the KTH person. And then you go over k minus one person and you kill the k person. The process continues along the circle until only one person is left, and that person can continue to live. The question is, given the sum, where to stand in order to avoid execution in the first place.

Today the general description of Joseph’s ring problem is:

There are N people in a room, all of them form a circle and start counting clockwise. Each time M reports, they quit the game. The next person who quits the game starts counting again, the person who reports for M quits again, and so on, until there is only one person left in the game, what is the number of the last person?

Circular linked list

The solution idea of circular linked list is relatively simple, just need to convert the problem description into code. N people in the room form a list of length N, end to end to form a circular list. The value of each item in the list is the number of each person. When the number reaches M, the item (denoted as X) is removed, that is, the next before the item no longer points to X, but x. Next. Iterate through the list until there is only one item left.

Let’s look at the code implementation.

Function createList(num) {createNode(value) {return {value: value, next: // let head = createNode(1); let node = head; For (let I = 2; i <= num; i++) { node.next = createNode(i); node = node.next; } // The last node points to the head node, forming a circular list node.next = head; return head; } function deleteListNode(num, NTH) {let node = createList(num); While (num >1) {for (let I = 1; i <= nth - 1; I ++) {if (I == nth-1) {// I is nth-1, then Node.next is the NTH node. Select node.next node.next = node.next-next; // List length -- num--; } node = node.next; Return node.value} //deleteListNode(m,n) to obtain the final resultCopy the code

Orderly array

The ordered array is used to simulate the circular linked list. The remaining array items after the first iteration of the array are removed to form a new array, and then a new round of iteration is carried out to remove the new array, and the loop is carried out until the array length is 1.

Let’s look at the code implementation.

function jhonRing(num, nth) { let arr = []; // create ordered array for (let I = 1; i <= num; i++) { arr[i - 1] = i; While (arr.length >= NTH) {let newArr = []; Let times = arr. Length - arr. Length % NTH; let times = arr. Slice (times) arr.slice(0, times).map((item, index) => {if ((index + 1) % NTH! == 0) { newArr.push(item) } }) arr = newArr; } // If the length of the array is less than NTH, the array needs to loop over to find the data to cull. While (arr. Length > 1) {let index = NTH % arr. Length - 1; Let newArr = arr.slice(index + 1).concat(arr.slice(0, index)); arr = newArr; }} //jhonRing(num, NTHCopy the code

Using ordered arrays to simulate linked lists looks the same, the time complexity looks the same, and even the code is not as clean, but why bother? The advantage of this method is reflected in the case of M>>N, the ordered list can effectively reduce the number of loops through the mode of mod. Taking N as 3 and M as 100 as an example, the linked list needs to iterate 100/3+1 times, while the ordered array can directly obtain the data to be deleted with subscript 0 according to the result of the mod operation 100/3-1=0.

Mathematics recursive

It is easy to fail to find an effective rule summary route when solving Joseph’s ring problem with mathematical problems. The following takes M=3 as an example to describe the detour when summarizing the rule. (Skip the invalid ideas and go straight to the valid ideas below)

  • Comparison of results with small amounts of multiple data (❌)
N = 1, f (1, 3) = 1; N = 2, f (2, 3) = 2; N = 3, f (3, 3) = 2; N = 4, f (4, 3) = 1; N = 5, f (5, 3) = 4; N = 6, f (6, 3) = 1; N = 7, f (7, 3) = 4; N = 8, f = 7 (8, 3); N = 9, f (9, 3) = 1; N = 10, f (10, 3) = 4;Copy the code

Through examples, it is found that the final result is not always between some numbers, except 1, 2, and 4, and 7 also appears. Then the subsequent results may have a similar situation, that is, the final result is not always limited to a certain number. F (3,3), f(6,3), f(9,3) and other N multiples of M do not get the same results, so there is no special relationship between the final results and multiples of 3. Therefore, it is not appropriate to search for rules by accumulating results with a small amount of comparative data.

  • Compare the relationship between the previous culling data (❌)
1, 2, 3, 4........ N-2, n-1, N // The number of the first deletion is M or M%N, which can be summarized as M%N and denoted as K. Then the sequence of the second deletion becomes K+1,K+2,....... N, 1, 2,... K - 1 / / is the second time to eliminate the Numbers for K + M % (N - 1) | | M % (N - 1) - (N - K - 1) in accordance with this law When N - > M (K + 1) % (N - 1), f (N) = f (N - 1) + M % (N - (N - 1)) When N - (K + 1) < M % (N - 1), f (N) = M % (N - (N - 1) - (N - f (N - 1) - 1)Copy the code

According to this rule, the result obtained without the second cycle is correct, and the result obtained after the second cycle is wrong. The fundamental reason is that the data after entering the second lap is no longer continuous, and the data removed from the first lap will affect the results of the second lap, so this scheme is not suitable.

  • Top-down analysis and bottom-up solution (✅)

The problem of Joseph’s ring is analyzed by recursion. Take N=10, M=3 as an example.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 // Call the last person out f(10,3) // After 10 people are numbered, after the first person out, Get the new queue and its numbers 3, 4, 5, 6, 7, 8, 9, 0, 1 // To make the new queue numbers continuous, we can call the new queue A, 3, 4, 5, 6, 7, 8, 9, 10%, 10, 11%10 // If we call an ordinary queue of 9 people B, Write the final result of 0,1,2,3,4,5,6,7,8 as f(9,3), then the result of the new queue A can be expressed as (f(9,3)+3)%. Then the result of the 9-person queue after playing the game according to the rule of N=9,M=3 and the initial number of 3 must be the same as the last person in the queue of N=10,M=3 and the initial number of 0. F (10,3)=(f(9,3)+3)%10Copy the code

Based on the above, it can be concluded that F (N,M)=(f(n-1,M)+M)%N. The final numbering result is f(N,M)+1.

Why can’t we start numbering at one? Because the result of the mod is starting at 0.

function Josephus(num,nth){ if(num==1){ return 0; }else{return (Josephus(num-1, NTH)+ NTH)%num}} //Josephus(N,M)+1Copy the code

Let’s optimize the recursive function

function JosephusR(num,nth){ let value = 0; for(let i=1; i<=num; If num =(value+ NTH)% I; if num =(value+ NTH)% I; } return value+1; } //JosephusR(N,M) is the final numberCopy the code

conclusion

The time complexity of Joseph’s ring problem is reduced from O(Mn) to O(n) by mathematical recursive optimization. It is certainly the fastest and easiest way to solve a problem through a circular linked list, but this mathematical recursion is more valuable for solving such algorithmic problems.