"Josephus-problem" pythonでリストを使う

Question

Pythonのリストを使ってJosepheusの問題を解決できるかどうかを知りたかったのですが、

簡単な言葉で言えば、ジョセフ問題は、事前に知られているスキップパラメータを使用して実行が処理された場合に安全となる環状配列内の位置を見つけることに関するものです。

例えば、[1,2,3,4,5,6,7]のような循環配置が与えられ、スキップパラメータが3の場合、人は3,6,2,7,5,1の順番で実行され、位置4は安全です。

私はしばらくの間このリストを使用して解決しようとしていましたが、インデックスの位置は扱いにくくなりました。

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 

コードスニペットで質問を更新しました、しかし、私は私のロジックが正しいとは思いません。

Answer 1

単純に、list.pop(i)を使用して、各犠牲者を削除して（自分のIDを取得する）ループ内で使用できます。それで、インデックスを折り返すことを心配するだけです。スキップされたインデックスの数を残っている囚人の数だけ取ることでできます。

それでは、質問の解決策は、

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] 

テスト出力になります：

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

Answer 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 

あなたが指数を計算したくない場合は、あなたがdequeデータ構造を使用することができます。

Answer 3

これは、あなたの質問に私のソリューションです：

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

Answer 4

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)