Three JavaScript methods to solve the Joseph ring problem

Overview

The Joseph Ring Problem, also known as the Joseph Murder Problem or the Lost Handkerchief Problem, is a classic algorithmic problem. There are many variations in the problem description, but the general idea of ​​solving the problem is the same. This article will solve the Joseph ring problem in three ways: circular linked list, ordered array, and mathematical recursion.

Problem Description

Let’s first take a look at what is the Joseph ring problem?

After the Romans occupied Chotapater, 39 Jews hid in a cave with Josephus and his friends. The 39 Jews decided that they would rather die than be caught by the enemy, so they decided on a method of suicide. The 41 people stood in a circle, and the first person started counting. Every time the third person counted, that person had to commit suicide, and then the next person would count again until everyone committed suicide. However, Josephus and his friends did not want to comply. Start with one person, skip k-2 people (because the first person has been skipped), and kill the kth person. Then, skip k-1 people and kill the kth person. This process continues in a circle until finally only one person is left, and that person can continue to live. The question is, given and , where to stand at the beginning to avoid being executed.

Today, the description of the Joseph ring problem generally becomes:

There are N people in a room. Everyone sits in a circle and starts counting clockwise. Every time the person who counts M, he or she exits the game. The next person who exits the game starts counting again, and the person who reports M exits again, and this cycle continues until there is only one person left in the game. What is the number of the last person?

Circular Linked List

The solution to the circular linked list problem is relatively simple. You only need to convert the problem description into code. The N people in the room form a linked list of length N, which are connected end to end to form a circular linked 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 of the previous item of the item no longer points to x, but to x.next. Traverse the linked list in this way until there is only one item left in the linked list.

Let's take a look at the code implementation.

function createList(num) {
    //Data structure of linked list nodes function createNode(value) {
        return {
            value: value,
            next: ''
        }
    }
    //List head node let head = createNode(1);
    let node = head;
    //Create associations between nodes after the head node 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 linked list node.next = head;
    return head;
}
function deleteListNode(num, nth) {
    //Create a circular linked list with data length num let node = createList(num);
    //When the length of the linked list is > 1, continue to the next round while (num > 1) {
        for (let i = 1; i <= nth - 1; i++) {
            if (i == nth - 1) {
                //If i is nth-1, then node.next is the nth node. Eliminate node.next
                node.next = node.next.next;
                // Link list length --
                num--;
            }
            node = node.next;
        }
    }
    //The value of the last remaining node is the last person's number return node.value
}
//deleteListNode(m,n) to get the final result

Ordered Array

Use an ordered array to simulate a circular linked list. After the first traversal and elimination of the array, the remaining array items are formed into a new array. Then a new round of traversal and elimination is performed on the new array, and this cycle is repeated until the array length is 1.

Let's take a look at the code implementation.

function jhonRing(num, nth) {
    let arr = [];
    //Create an ordered array for (let i = 1; i <= num; i++) {
        arr[i - 1] = i;
    }
    //When the array length is greater than nth, the array can be found without looping through the data to be removed while (arr.length >= nth) {
        let newArr = [];
        //Move the remaining data at the end of the array to the front of the new array, and start a new round of traversal from the generated data let times = arr.length - arr.length % nth;
        newArr = arr.slice(times)
        arr.slice(0, times).map((item, index) => {
            //Add all data except the removed data to the new array if ((index + 1) % nth !== 0) {
                newArr.push(item)
            }
        })
        arr = newArr;
    }
    //When the array length is less than nth, the array needs to be traversed in a loop to find the data to be removed. The modulo operation can reduce the number of traversals while (arr.length > 1) {
        // Take the remainder to get the index of the data to be removed let index = nth % arr.length - 1;
        //Remove the second half of the data and combine it with the first half to form a new array let newArr = arr.slice(index + 1).concat(arr.slice(0, index));
        arr = newArr;
    }
}
//jhonRing(num, nth) to get the final result

The operation of simulating a linked list with an ordered array seems to be similar to that of a linked list, the time complexity seems to be the same, and even the code is not as concise as that of a linked list, but why do we still propose this method? The advantage of this method is that when M>>N, the ordered linked list effectively reduces the number of times the array is traversed by taking the remainder. Taking N as 3 and M as 100 as an example, the linked list needs to be traversed 100/3+1 times, while the ordered array directly obtains the index of the data to be removed as 0 based on the result of the modulo operation 100/3-1=0.

Mathematical recursion

It is very easy to fail to find an effective way to summarize the rules when solving the Joseph ring problem with mathematical problems. Below, we use M=3 as an example to illustrate the detours we took when summarizing the rules. (You can skip the invalid ideas and read the valid ideas below)

Compare multiple results with smaller data volumes (❌)

When N=1, f(1,3)=1;
When N=2, f(2,3)=2;
When N=3, f(3,3)=2;
When N=4, f(4,3)=1;
When N=5, f(5,3)=4;
When N=6, f(6,3)=1;
When N=7, f(7,3)=4;
When N=8, f(8,3)=7;
When N=9, f(9,3)=1;
When N=10, f(10,3)=4;

Through examples, we can find that the final result is not always between certain numbers. In addition to 1, 2, and 4, 7 also appears, and the subsequent results may also have similar situations, that is, the final result is not always limited to a certain number. f(3,3) f(6,3) f(9,3) etc. when N is a multiple of M do not produce the same results, which shows that there is no special connection between the final result and the multiple of 3. Therefore, it is not appropriate to find patterns by accumulating and comparing the results when the amount of data is small.

Compare the relationship between the previous elimination data (❌)

//Number N people from 1 to N
1, 2, 3, 4........N-2, N-1, N
//The first elimination number is M or M%N, which can be summarized as M%N and recorded as K. Then the sequence for the second elimination becomes
K+1,K+2,.......N,1,2......K-1
//The number of the second elimination is K+M%(N-1) || M%(N-1)-(NK-1)
According to this rule, when N-(K+1)>M%(N-1), f(n)=f(n-1)+M%(N-(n-1))
When N-(K+1)<M%(N-1), f(n)=M%(N-(n-1))-(Nf(n-1)-1)

By calculating according to this rule, we can find that the result obtained before the second round of traversal is correct, but the result after the second round of traversal is wrong. The fundamental reason is that the data after entering the second round is no longer continuous. The data eliminated during the first round of traversal will affect the results of the second round of traversal, so this solution is not suitable.

Analyze problems from top to bottom and solve them from bottom to top (✅)

Use recursive thinking to analyze the Joseph ring problem. Take N=10 and M=3 as an example for analysis.

//Number the 10 people starting from 0 (I will explain later why we cannot start numbering from 1)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
//Record the number of the last person to leave the queue as f(10,3)
//After 10 people are numbered, the first person leaves the queue and gets a new queue and number
3, 4, 5, 6, 7, 8, 9, 0, 1
//In order to make the number of the new queue continuous, we can record the new queue as A and write
3, 4, 5, 6, 7, 8, 9, 10%10, 11%10
//If a normal queue of 9 people is recorded as B, and the final result of writing 0,1,2,3,4,5,6,7,8 is recorded as f(9,3), then the result of the new queue A can be expressed as (f(9,3)+3)%10
//The 9-person queue A is obtained by removing one person from the 10-person queue. Then the result of the 9-person queue playing the game according to the rules of N=9, M=3, and initial number 3 must be the same as the last person to leave the queue of N=10, M=3, and initial number 0.
//Therefore, there is a relationship between the number of the last person to leave the queue of 10 and the number of the person to leave the queue A of 9 people f(10,3)=(f(9,3)+3)%10

Based on the above, we can conclude that f(N,M)=(f(N-1,M)+M)%N. The final numbering result is f(N,M)+1.
Why can't the numbering start from 1? Because the return result of the remainder operation starts from 0.

function Josephus(num,nth){
    if(num==1){
        return 0;
    }else{
        return (Josephus(num-1,nth)+nth)%num
    }
}
//Josephus(N,M)+1 is the final number

Optimize the recursive function

function JosephusR(num,nth){
    let value = 0;
    for(let i=1;i<=num;i++){
        //Here is the modulus of i. In the above recursion, num is also gradually getting smaller, so here is i instead of num
        value=(value+nth)%i;
    }
    return value+1;
}
//JosephusR(N,M) is the final number

Summarize

Through mathematical recursive optimization, the time complexity of the Joseph ring problem is reduced from the original O(mn) to O(n). Solving the problem through a circular linked list is indeed the fastest and easiest way of thinking, but this mathematical recursive method is more valuable for solving such algorithmic problems.

This concludes the article on three JavaScript methods for solving the Joseph ring problem. For more JavaScript Joseph ring content, please search previous articles on 123WORDPRESS.COM or continue browsing the following related articles. I hope you will support 123WORDPRESS.COM in the future!