递归排列生成器，交换列表项无效

Question

我想系统地生成字母的排列组合。 我不想使用 Python 的 itertools.permutation，因为预先生成每一种排列会导致我的电脑崩溃（第一次让我电脑强制关机，真是太厉害了）。

所以，我的新方法是实时生成和测试每一个排列。目前，我尝试用递归来处理这个问题。

我的想法是从最大的列表开始（我用一个包含3个元素的列表作为例子），递归缩小到只有两个元素的列表。然后，它会打印这个列表，交换最后两个元素，再打印一次，然后返回到上一级，重复这个过程。

比如，对于123：

123（将位置0和位置0交换）

    23    --> 123 (swap position 1 with position 1)
    32    --> 132 (swap position 1 with position 2)

213（将位置0和位置1交换）

    13    --> 213 (swap position 1 with position 1)
    31    --> 231 (swap position 1 with position 2)

321（将位置0和位置2交换）

    21    --> 321 (swap position 1 with position 1)
    12    --> 312 (swap position 1 with position 2)

对于一个四个字母的数字（1234）：

1234（将位置0和位置0交换）

    234    (swap position 1 with position 1)

           34 --> 1234
           43 --> 1243
    324    (swap position 1 with position 2)
           24 --> 1324
           42 --> 1342
    432    (swap position 1 with position 3)
           32 --> 1432
           23 --> 1423

2134（将位置0和位置1交换） 134（将位置1和位置1交换） 34 --> 2134 43 --> 2143 314（将位置1和位置2交换） 14 --> 2314 41 --> 2341 431（将位置1和位置3交换） 31 --> 2431 13 --> 2413

这是我目前为递归写的代码，但这让我很头疼，递归不是我的强项。这是我写的代码。

def perm(x, y, key):
    print "Perm called: X=",x,", Y=",y,", key=",key
    while (x<y):

        print "\tLooping Inward"

        print "\t", x," ",y," ", key
        x=x+1
        key=perm(x, y, key)
        swap(x,y,key)
        print "\tAfter 'swap':",x," ",y," ", key, "\n"

    print "\nFull Depth Reached"
    #print key, " SWAPPED:? ",swap(x,y,key)
    print swap(x, y, key)
    print " X=",x,", Y=",y,", key=",key
    return key

def swap(x, y, key):
    v=key[x]
    key[x]=key[y]
    key[y]=v
    return key

任何帮助都非常感谢，这是一个很酷的项目，我不想放弃它。

谢谢大家！欢迎对我的方法或其他任何事情发表评论。

Answer 1

我觉得你的想法很好，但要跟踪位置可能会有点麻烦。通常生成排列的方法是用一个函数，这个函数需要两个字符串作为参数：一个是要去掉字符的字符串（str），另一个是要添加字符的字符串（soFar）。

在生成排列时，我们可以想象从 str 中取出字符，然后把它们加到 soFar 中。假设我们有一个叫 perm 的函数，它接受这两个参数，并找到 str 的所有排列。接下来，我们可以考虑当前的字符串 str。我们会有以 str 中每个字符开头的排列，所以我们只需要遍历 str，用每个字符作为起始字符，然后对剩下的字符调用 perm：

// half python half pseudocode    
def perm(str, soFar):
    if(str == ""):
        print soFar // here we have a valid permutation
        return

    for i = 0 to str.length:
        next = soFar + str[i]
        remaining = str.substr(0, i) + str.substr(i+1)
        perm(remaining, next)

Answer 2

在我职业生涯的后期，我偶然发现了我以前的问题。

为了高效地完成这个任务，你需要写一个生成器。

与其一次性返回所有的排列组合（这需要把所有的结果都存储在内存里），生成器则是每次返回一个排列组合（这个列表中的一个元素），然后暂停，等你需要下一个时再计算出来。

生成器的好处有：

• 占用的空间更少。
  • 生成器只占用大约40到80个字节的空间。一个生成器可以生成数百万个项目。
  • 一个只有一个元素的列表占用40个字节，而一个有1000个元素的列表则占用4560个字节。
• 更高效
  • 只计算你需要的值。如果在排列字母时，正确的排列在列表的前面找到了，那么花费在生成其他排列上的时间就是浪费的。

(Itertools.permutation就是一个生成器的例子)

我该如何写一个生成器？

在Python中写生成器其实非常简单。
基本上，你可以写一些代码来生成排列组合的列表。现在，不要写 resultList+=[ resultItem ]，而是写 yield(resultItem)。

这样你就创建了一个生成器。如果我想遍历我的生成器，我可以写

for i in myGenerator:

就这么简单。

下面是我很久以前尝试写的一个生成器的代码：

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return