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

问题:

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.

回答1:

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

回答2:

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.

回答3:

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

回答4:

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())

回答5:

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)