Josephus Problem Simulation

Josephus Problem Simulation

Problem description

Josephus problem is a famous theoretical problem in mathematics and computer science. It describe such a situation:

There are N people standing in a circle waiting to be executed. Proccess beging at certain person in the circle, in each round, it skip the first M-1 person and the Mth person is killed, then the proccess continue from the next person. Obviously, one person is killed in each round, so after N-1 round, N-1 people get killed and the last person remains, who will be given freedom.

Solution in python

we can simulate the josephus problem using dynamic array or circular linked list.

Dynamic array

def josephus_problem_with_dynamic_array(n, k):
    index_arr = [i for i in range(1, n+1)]
    person_pointer = 0
    step_count = 1
    while len(index_arr) > 1:
        if step_count == k:
            # remove the killed person from index arr
            index_arr.pop(person_pointer)
            person_pointer -= 1
        person_pointer = (person_pointer + 1) % len(index_arr)
        step_count = step_count % k + 1
    return index_arr[0]

Circular linked list

def josephus_problem_with_circular_linked_list(n, k):
    class Node(object):
        def __init__(self, index, next=None):
            self.index = index
            self.next = next
    # initialize circular linked list
    circular_linked_list = Node(1)
    last_node = circular_linked_list
    for i in range(2, n+1):
        tmp = Node(i)
        last_node.next = tmp
        last_node = tmp
    last_node.next = circular_linked_list
    current_node = circular_linked_list
    step_count = 1
    while current_node.next != current_node:
        if step_count == k:
            # remove list node
            current_node = current_node.next
            last_node.next = current_node
        else:
            last_node = current_node
            current_node = current_node.next
        step_count = step_count % k + 1
    return current_node.index
Current rating: 5

Comments

ADDRESS

  • Email: jimmykobe1171@126.com
  • Website: www.catharinegeek.com