停止递归生成器和排列

作为一项练习，我一直在尝试各种方式来生成Python中列表的所有排列 - 递归，非递归... - 并将性能与itertools.permutations()进行比较。但我在使用递归方法，它不与StopIteration异常干净完成，而是的发电机版本麻烦抛出一个IndexError：停止递归生成器和排列

def spawnperms(alist): 
    """same algorithm as recursive option, but a generator""" 
    if (alist == []): 
     yield [] 
    for perm in spawnperms(alist[:-1]): 
     for i in range(len(perm)+1): 
      yield perm[:i] + [alist[-1]] + perm[i:]

从Python解释器调用此：

>>> for i in spawnperms(range(3)): 
...  print i 
... 
[2, 1, 0] 
[1, 2, 0] 
[1, 0, 2] 
[2, 0, 1] 
[0, 2, 1] 
[0, 1, 2] 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "<stdin>", line 5, in spawnperms 
    File "<stdin>", line 5, in spawnperms 
    File "<stdin>", line 5, in spawnperms 
    File "<stdin>", line 7, in spawnperms 
IndexError: list index out of range

Ouch。我尝试着用pdb来完成它，它几乎在我的大脑中创建了一个堆栈溢出，但是我的理解是递归“向下”到空列表，然后外部（我认为）for循环用完索引。

如何更正我的代码？

编辑：马克拜尔斯看似简单的正确答案一个学习就是干净的编码习惯，可以防止错误。如果我在if之后系统地使用了else，无论我是否认为可以重新访问该状况，都不会发生这种情况。它仍然感觉非常愚蠢！

来源

2010-08-10 chryss

要测试列表是否为空，“if not alist：”就足够了。 – kennytm 2010-08-10 11:09:07

是的，的确如此。我通常会这样做，但专注于其他事情。不过，你是完全正确的。 – chryss 2010-08-10 11:30:42

你缺少一个else：

if (alist == []): 
    yield [] 
else: 
    for ...

这是因为yield不会以同样的方式作为return行为。当您请求下一个值时，在yield语句后继续执行。

来源

2010-08-10 11:07:50

嗯......毫无疑问，“yield”和“return”之间的区别正是我认为我不需要“else”的原因。但我认为我的逻辑是有缺陷的。 – chryss 2010-08-10 11:09:27

:)是的，我的逻辑完全有缺陷。非常感谢 - 我现在觉得多么愚蠢。 – chryss 2010-08-10 11:11:12

停止递归生成器和排列

回答

相关问题