如何解决在Python的约瑟夫拼图？

Question

我想代表在Python中Josephus problem。简单地说，给定一个列表items，每k个元素访问/标记，直到没有项目“不变”。如何以这种方式遍历列表并查看最后一个未触及的元素是什么？

我的代码是：

def josephus(items,k): 
    while len(items)>1: 
     del items[k] 
    return items 

但是，当我试图

print(josephus([1,2,3,4,5,6,7,8,9,10],2)) 

它返回：

line 3, in josephus 
    del items[k] 
IndexError: list assignment index out of range 

你能帮助我。该代码有什么问题？

Answer 1

您试图在索引2删除的项目，但你已经删除了该项目。

Python的索引从0 开始，不为1，所以2是第三项。换句话说，列表[1, 2]具有的长度长于1（有2项），但是只有索引0和1在该列表中存在。

你可以添加打印到你的循环，看看发生了什么：

def josephus(items, k): 
    while len(items) > 1: 
     print(items) 
     del items[k] 
    return items 

和调用函数与略短名单，以保持输出管理：

>>> josephus([1,2,3,4], 2) 
[1, 2, 3, 4] 
[1, 2, 4] 
[1, 2] 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "<stdin>", line 4, in josephus 
IndexError: list assignment index out of range 

这说明你是每次删除第三个项目，并且只剩下两个项目时抛出错误。

代替硬编码的长度，你可以测试一个长度超过k更大：

def josephus(items, k): 
    while len(items) > k: 
     del items[k] 
    return items 

现在循环条件，保证有索引k元素删除：

>>> def josephus(items, k): 
...  while len(items) > k: 
...   del items[k] 
...  return items 
... 
>>> josephus([1,2,3,4], 2) 
[1, 2] 

这然而，要删除给定索引之后的所有内容，还有很多工作要做。只需使用一个片：

def josephus(items, k): 
    del items[k:] 
    return items 

的[k:]符号告诉Python来解决所有项目开始于索引k直到列表的末尾（也就是:后无数值）。

不过，如果你都应该删除每个k个元素（所以每2或3等），然后你会了解它的错误的方式。再次使用切片表示法：

del items[::k] 

我填写片的插槽方面，步幅。这将删除元素0 + 0 * k，并且0 + 1 * k和0 + 2 * k等：

>>> items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
>>> items[::2] 
[1, 3, 5, 7, 9] 
>>> del items[::2] 
>>> items 
[2, 4, 6, 8, 10] 

如果你想实现Josephus problem你不能用它来删除的项目，如删除必须是圆形，至少在没有计算下一轮抵消的新起点。使用%模运算去绕了一圈，调整变化长度：

def josephus(items, k): 
    skip = k - 1 # deletion removes the item, so skip k - 1 
    index = skip % len(items) 
    while len(items) > 1: 
     del items[index] 
     index = (index + skip) % len(items) 
    return items[0] 

请注意，我现在返回一个幸存的项目，不在名单。

该代码保持跟踪下一个项目在index删除。我们从k - 1开始调整基于0的索引;第二项是在1。然后，我们围绕“圈子”，通过递增k - 1的步骤，因为我们刚刚删除了k这个项目，并且之后的所有内容都会向上移动一圈，并使用%来回卷到列表的开头。

Answer 2

您需要> K：

while len(items) > k: 

最后价值的物品前的错误是[1, 2]所以items[2]-> IndexError为您正试图指数两个元素的列表的第三个元素。

def josephus(items, k): 
    while len(items) > k: 
     del items[k] 
    return items 

输出：

In [27]: josephus([1,2,3,4,5,6,7,8,9,10],2) 
Out[27]: [1, 2] 

如果你想以2比意味着你将需要从K至-1第二个索引：

def josephus(items, k): 
    while len(items) >= k: 
     del items[k-1] 
    return items 

现在你会得到一个单一的元素：

In [29]: josephus([1,2,3,4,5,6,7,8,9,10],2) 
Out[29]: [1] 

要删除k'th元素：

def josephus(items, k): 
    if 0 <= k < len(items): 
     del items[k] 
    return items 

Answer 3

如果你想删除原来的列表中的每个k值开始在指数i，只是做

del items[i::k] 

在特定情况下，它看起来像要删除项目k第一，所以做：

del items[k-1::k] 

这是如此简单，你WOU ldn't包装在一个功能，但如果你想：

def josephus(items,k): 
    del items[k-1::k] 
    return items