如何用Python解决Josephus谜题？

Question

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

我的代码是：

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

但是，当我试图

^{pr2}$

它返回：

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

你能帮帮我吗。那密码怎么了？在

Answer 1

您需要>；k：

 while len(items) > k:

错误之前的最后一个值项是[1, 2]所以items[2]-> IndexError，因为您正试图索引两个元素列表的第三个元素。在

^{pr2}$

输出：

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 2

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

Python索引从0开始，而不是1，因此2是第三个项。换句话说，列表[1, 2]的长度大于1（有2个项），但该列表中只存在索引0和{}。在

您可以将打印添加到循环中以查看发生了什么：

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

并使用略短的列表调用函数以保持输出的可管理性：

^{pr2}$

这表明您每次都在删除第3项，当只剩下2项时会抛出错误。在

您可以测试大于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个元素（所以每第二个或第三个元素，等等），那么您就走错了方向。再次使用切片表示法：

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]

注意，我现在返回的是一个幸存的项目，而不是列表。在

代码跟踪要在^{中删除的下一个项。我们从k - 1开始调整基于0的索引；第二项位于1。然后，我们通过递增k - 1步来绕着这个“圆”，因为我们刚刚删除了第k项，之后的所有内容都将围绕着圆圈上移一步，并使用%返回到列表的开头。在

Answer 3

如果您想删除从索引i开始的原始列表中的每个k值，只需这样做

del items[i::k]

在您的特定情况下，看起来您想先删除项目k，因此请执行以下操作：

^{pr2}$

这非常简单，您不会将其包装在函数中，但如果您想：

要将其包装在函数中：

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