使用python中的列表的"约瑟夫问题"

Question

我想知道是否有可能使用python中的list来解决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).然后,我们只需要担心包装索引,你可以通过跳过索引mod来保留剩余囚犯的数量.

那么,问题解决方案就变成了

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数据结构。