能有人解释一下这个Python排列代码吗？

Question

我在这里看到了一些关于排列组合的代码，但我一直找不到一个好的逐步讲解，能让我明白到底发生了什么。如果有人能解释一下这段代码每一步在做什么，我会非常感激。我总是搞不清楚。我要看的代码是用Python写的，来自http://snippets.dzone.com/posts/show/753。

def all_perms(str):
    if len(str) <=1:
        yield str
    else:
        for perm in all_perms(str[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]


for p in all_perms(['a','b','c']):
    print p

Answer 1

你看到的这个是一个迭代器生成器。它是一个函数，可以返回一个可以被循环遍历的对象。

在执行for循环的时候，all_perms会一直执行，直到遇到一个yield。这个yield返回的值会被传递给循环，作为p这个变量。然后，all_perms会在上次退出yield语句后的位置继续执行。

Answer 2

def all_perms(str):
    # If there is only one item, there can be only one permutation
    # yield the single item
    if len(str) <=1:
        yield str
    else:
        # loop over the permutations returned by a recursive call to all_perms
        # note it is passing a subset of the list passed in.
        for perm in all_perms(str[1:]):
            # for each returned sub-permutation insert the item that
            # wasn't passed into each possible position.
            for i in range(len(perm)+1):
                yield perm[:i] + str[0:1] + perm[i:]


for p in all_perms(['a','b','c']):
    print p

你传入了 ['a','b','c']。

然后它会调用 all_perms(['b', 'c'])，接着又会调用 all_perms(['c'])，这时候会返回 'c'。

这里的 yield 语句意味着 all_perms() 是一个 生成器，而它自己调用自己则说明它在使用 递归。

我建议你使用 itertools.permutations，而不是那段代码。

Answer 3

首先，参数名 str 其实取得不好。这个名字可能是因为它在 Python 中适用于所有类型的序列，但更好的名字应该是 seq 或者其他能更清楚表达意思的名字。

1. 如果列表的长度小于等于 1（也就是空列表或者只有一个元素），那么直接返回这个列表（这种情况只有一种解决方案）。

2. 对于其他情况：

   a) 先创建去掉第一个元素后的所有排列组合，也就是 str[1:] 的所有排列。

   b) 然后把第一个元素插入到每一个排列的每个位置，最后返回结果。

yield 的工作方式有点像 return；主要的区别在于，yield 会返回当前的值，并且当函数再次被调用时，会从 yield 之后的指令继续执行。

这样做可以很方便地组装结果。

举个例子：

'a' 直接返回 'a'（这很简单）。'ab' 首先去掉头部的 'a'，然后创建 b 的所有排列（只有一个，就是 'b' 本身）。接着把头部元素放到每个位置，最后得到 'ab'（头部+列表）和 'ba'（列表+头部）。

等等。