递归排列生成器，交换列表项不起作用

Question

我想系统地生成字母表的排列。 我不能不想使用 python itertools.permutation，因为预先生成每个排列的列表会导致我的计算机崩溃（我第一次真正用它来强制关闭，这非常棒）。

因此，我的新方法是动态生成和测试每个密钥。目前，我正在尝试用递归来处理这个问题。

我的想法是从最大的列表开始（我将使用 3 元素列表作为示例），递归到较小的列表，直到列表有两个元素长。然后，它将打印列表，交换最后两个，再次打印列表，然后返回上一级并重复。

例如，对于 123

123（位置0与位置0交换）

<前><代码> 23 --> 123（位置 1 与位置 1 交换） 32 --> 132（位置 1 与位置 2 交换）

213（位置 0 与位置 1 交换）

<前><代码> 13 --> 213（位置 1 与位置 1 交换） 31 --> 231（位置 1 与位置 2 交换）

321（位置 0 与位置 2 交换）

<前><代码> 21 --> 321（位置 1 与位置 1 交换） 12 --> 312（位置 1 与位置 2 交换）

对于四字母数字 (1234)，

1234（位置0与位置0交换）

 234（位置 1 与位置 1 交换）

           34 --> 1234
           43 --> 1243
    324（位置 1 与位置 2 交换）
           24 --> 1324
           42 -->第1342章
    432（位置 1 与位置 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

在我职业生涯后期遇到了我的老问题

为了有效地做到这一点，您需要编写一个生成器。

生成器不是返回所有排列的列表（这需要将它们（全部）存储在内存中），而是返回一个排列（此列表的一个元素），然后暂停，然后当您要求时计算下一个。

发电机的优点是：

• 占用空间少得多。
  • 生成器占用 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

Answer 2

我认为你的想法非常好，但是跟踪位置可能会有点难以处理。我见过的递归生成排列的一般方法是一个接受两个字符串参数的函数：一个用于从 (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)