递归置换生成器，交换列表项不能工作

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

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 bytes

​

• 更有效的
  • 只计算所需的值。在排列字母表时，如果在列表结束前找到了正确的排列，则生成所有其他排列的时间是wasted.

。

​

(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)