"Josephus-p‌r‌o‌b‌l‌e‌m" using list in python

Question

I wanted to know if it will be possible to solve the Josepheus problem using list in python.

In simple terms Josephus problem is all about finding a position in a circular arrangement which would be safe if executions were handled out using a skip parameter which is known beforehand.

For eg : given a circular arrangement such as [1,2,3,4,5,6,7] and a skip parameter of 3, the people will be executed in the order as 3,6,2,7,5,1 and position 4 would be the safe.

I have been trying to solve this using list for some time now, but the index positions becomes tricky for me to handle.

 a=[x for x in range(1,11)]
 skip=2
 step=2
 while (len(a)!=1):
   value=a[step-1]
   a.remove(value)
   n=len(a)
   step=step+skip
   large=max(a)
   if step>=n:        
      diff=abs(large-value)
      step=diff%skip
   print a

Updated the question with code snippet, but i don't think my logic is correct.

nneonneo · Accepted Answer · 2020-09-15T07:18:42.620

20

Quite simply, you can use list.pop(i) to delete each victim (and get his ID) in a loop. Then, we just have to worry about wrapping the indices, which you can do just by taking the skipped index mod the number of remaining prisoners.

So then, the question solution becomes

def josephus(ls, skip):
    skip -= 1 # pop automatically skips the dead guy
    idx = skip
    while len(ls) > 1:
        print(ls.pop(idx)) # kill prisoner at idx
        idx = (idx + skip) % len(ls)
    print('survivor: ', ls[0])

Test output:

>>> josephus([1,2,3,4,5,6,7], 3)
3
6
2
7
5
1
survivor:  4

edited Sep 15 '20 at 07:18

answered Sep 16 '12 at 07:10

nneonneo

171,345
36
312
383

2

This algorithm is amazing! Can you share that how did you come up with the `idx = (idx + skip) % len(ls)`? I know it works, but I have no ideas how people could find out this way. Thank you! – Jay Wang Jan 23 '16 at 15:58
1

@JayWong it's the best way to go through an array and wrap from the end to the beginning – Maria Ines Parnisari Dec 04 '16 at 02:56
how did you come up with such a intiutive approach so good i was brainstorming it for last few days – Aditya Sep 15 '20 at 05:54
This throws error when the skip is bigger number than length of the list. What would be a way to fix it ? – Ersin Nurtin Dec 08 '22 at 13:11
Yes, just take the initial index mod the length of the list. – nneonneo Dec 08 '22 at 18:12

score 5 · Answer 2 · answered Mar 11 '17 at 06:26

In [96]: def josephus(ls, skip):
    ...:     from collections import deque
    ...:     d = deque(ls)
    ...:     while len(d)>1:
    ...:         d.rotate(-skip)
    ...:         print(d.pop())
    ...:     print('survivor:' , d.pop())
    ...:     

In [97]: josephus([1,2,3,4,5,6,7], 3)
3
6
2
7
5
1
survivor: 4

If you do not want to calculate the index, you can use the deque data structure.

score 3 · Answer 3 · answered Jun 13 '19 at 21:47

My solution uses a math trick I found online here: https://www.youtube.com/watch?v=uCsD3ZGzMgE It uses the binary way of writing the number of people in the circle and the position where the survivor sits. The result is the same and the code is shorter.

And the code is this:

numar_persoane = int(input("How many people are in the circle?\n")) #here we manually insert the number of people in the circle

x='{0:08b}'.format(int(numar_persoane)) #here we convert to binary

m=list(x) #here we transform it into a list

for i in range(0,len(m)): #here we remove the first '1' and append to the same list

    m.remove('1')

    m.append('1')

    break

w=''.join(m) #here we make it a string again

print("The survivor sits in position",int(w, 2)) #int(w, 2) makes our string a decimal number

This doesn’t have a skip parameter and gives the wrong result for the sample parameters (n=7: this code gives 7 but the right answer is 4 or 3 depending on indexing convention). — nneonneo, Dec 08 '22 at 18:14
Ah, I see: this solution is only valid for skip=2. Although it's a nice solution, this is a crucial limitation. — nneonneo, Dec 12 '22 at 09:45

Idris · Answer 4 · 2021-05-19T15:26:52.317

2

if you are looking for the final result only, here is a simple solution.

def JosephusProblem(people):
  binary = bin(people)  # Converting to binary
  winner = binary[3:]+binary[2]  # as the output looks like '0b101001'. removing 0b and adding the 1 to the end
  print('The winner is',int(winner,2))  #converting the binary  back to decimal

If you are looking for the math behind this code, go check out this video: Josephus Problem(youTube)

edited May 19 '21 at 15:26

answered Oct 02 '19 at 18:06

Idris

29
1
6

This solution, like the one by George Florin, is only applicable for a skip of k=2, not a general solution to the problem. – nneonneo Dec 12 '22 at 09:46

score 1 · Answer 5 · answered Oct 24 '18 at 14:13

it looks worse but easier to understand for beginners

def last(n):
    a=[x for x in range(1,n+1)]
    man_with_sword = 1
    print(a)
    while len(a)!=1:   
        if man_with_sword == a[len(a)-2]:  #man_with_sword before last in circle
            killed = a[len(a)-1]
            a.remove(killed)
            man_with_sword=a[0]
        elif man_with_sword==a[len(a)-1]:  #man_with_sword last in circle
            killed = a[0]
            a.remove(killed)
            man_with_sword=a[0]
        else:
            i=0
            while i < (len(a)//2): 
                i=a.index(man_with_sword)
                killed = a[a.index(man_with_sword)+1]
                a.remove(killed)
                #pass the sword 
                man_with_sword=a[i+1] # pass the sword to next ( we killed next)
                print (a, man_with_sword) #show who survived and sword owner
                i+=1
        print (a, man_with_sword,'next circle') #show who survived and sword owner

score 1 · Answer 6 · edited Nov 24 '20 at 06:03

1

The total number of persons n and a number k, which indicates that k-1 persons are skipped and a kth person is killed in the circle.

def josephus(n, k): 
  if n == 1: 
    return 1
  else: 
    return (josephus(n - 1, k) + k-1) % n + 1

n = 14
k = 2            
print("The chosen place is ", josephus(n, k))

edited Nov 24 '20 at 06:03

Shaido

27,497
23
70
73

answered Jul 24 '19 at 12:57

Adarsh Pawar

682
6
15

Beautiful recursive solution – Federico Baù Nov 24 '20 at 05:52

score 0 · Answer 7 · edited Feb 11 '18 at 08:15

This is my solution to your question:

# simple queue implementation<ADT>
class Queue:
    def __init__(self):
        self.q = []
    def enqueue(self,data):
        self.q.insert(0,data)
    def dequeue(self):
        self.q.pop()
    def sizeQ(self):
        return len(self.q)
    def printQ(self):
        return self.q


lists = ["Josephus","Mark","Gladiator","Coward"]
to_die = 3
Q = Queue()
# inserting element into Q
for i in lists:
    Q.enqueue(i)
# for size > 1 
while Q.sizeP() > 1:
    for j in range(1,3): 
# every third element to be eliminated
         Q.enqueue(Q.dequeue())
    Q.dequeue()
print(Q.printQ())

There is another variation of Josephus problem , if counting starts Anti - Clockwise — bhushan jain, Feb 11 '18 at 03:30

score -1 · Answer 8 · answered Mar 05 '18 at 03:50

def Last_Person(n):
    person = [x for x in range(1,n+1)]
    x = 0
    c = 1
    while len(person) > 1:
        if x == len(person) - 1:
            print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[0])
            person.pop(0)
            x = 0
            c = c+1
        elif x == len(person) - 2:
            print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[x + 1])
            person.pop(x+1)
            x = 0
            c = c + 1
        else:
            print("Round ", c, "- Here's who is left: ", person, "Person ", person[x], "killed person", person[x + 1])
            person.pop(x + 1)
            x = x + 1
            c = c + 1
    print("Person", person[x], "is the winner")

Last_Person(50)

"Josephus-p‌r‌o‌b‌l‌e‌m" using list in python

8 Answers8

Linked