python itertools.permutations的算法

Question

有人能解释一下Python标准lib 2.6中itertools.permutations例程的算法吗？我不明白为什么会这样。

代码是：

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 1

你需要理解permutation cycles的数学理论，也就是所谓的“轨道”（了解两个“艺术术语”很重要，因为数学学科combinatorics的核心是相当高级的，你可能需要查找research papers，它可以使用两个术语中的任何一个）。

对于排列理论的简单介绍，wikipedia可以提供帮助。我提到的每一个网址都提供了合理的参考书目，如果你对组合数学足够着迷，想进一步探索它并获得真正的理解（我确实，个人——这对我来说已经成为一种爱好；-）。

一旦你理解了数学理论，代码仍然是微妙的和有趣的“逆向工程”。显然，indices只是当前对池中索引的排列，因为生成的项总是由

yield tuple(pool[i] for i in indices[:r])

所以这个迷人的机器的核心是cycles，它代表排列的轨道，并导致indices被更新，主要是通过语句

j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]

即，如果cycles[i]是j，这意味着索引的下一次更新是将第I个（从左侧）与第j个（从右侧）交换（例如，如果j是1，则indices的最后一个元素将被交换--indices[-1]）。然后，当cycles的某个项在递减期间达到0时，出现不太频繁的“批量更新”：

indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i

这将把i的第indices项放在最末尾，将下面所有的索引项左移一个，并指示下一次到达cycles项时，我们将把i的第indices项（从左）与n - i的第i项（从右）交换，这将再次成为i的第^{，当然，除了

cycles[i] -= 1

在我们下次检查之前；-）。

最困难的部分当然是证明这是有效的——即所有排列都是完全生成的，没有重叠，并且正确的“定时”退出。我认为，如果在简单的情况下完全公开，就可以更容易地了解机器的工作原理，而不是一个证明——注释掉yield语句并添加print语句（Python 2.*），我们可以

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)
    print 'I', 0, cycles, indices
    # yield tuple(pool[i] for i in indices[:r])
    print indices[:r]
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
        print 'B', i, cycles, indices
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
        print 'A', i, cycles, indices
            else:
        print 'b', i, cycles, indices
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
        print 'a', i, cycles, indices
                # yield tuple(pool[i] for i in indices[:r])
            print indices[:r]
                break
        else:
            return

permutations('ABC', 2)

运行此命令将显示：

I 0 [3, 2] [0, 1, 2]
[0, 1]
b 1 [3, 1] [0, 1, 2]
a 1 [3, 1] [0, 2, 1]
[0, 2]
B 1 [3, 0] [0, 2, 1]
A 1 [3, 2] [0, 1, 2]
b 0 [2, 2] [0, 1, 2]
a 0 [2, 2] [1, 0, 2]
[1, 0]
b 1 [2, 1] [1, 0, 2]
a 1 [2, 1] [1, 2, 0]
[1, 2]
B 1 [2, 0] [1, 2, 0]
A 1 [2, 2] [1, 0, 2]
b 0 [1, 2] [1, 0, 2]
a 0 [1, 2] [2, 0, 1]
[2, 0]
b 1 [1, 1] [2, 0, 1]
a 1 [1, 1] [2, 1, 0]
[2, 1]
B 1 [1, 0] [2, 1, 0]
A 1 [1, 2] [2, 0, 1]
B 0 [0, 2] [2, 0, 1]
A 0 [3, 2] [0, 1, 2]

关注cycles：它们从3开始，2——然后最后一个是递减的，所以3，1——最后一个还不是零，所以我们有一个“小”事件（索引中的一个交换）并中断内部循环。然后我们再次输入，这一次最后一个的减量是3，0，最后一个现在是0，所以这是一个“大”事件，指数中的“质量交换”（这里没有太多的质量，但是，可能有；-），循环回到3，2。但现在我们还没有中断for循环，所以我们继续将下一个递减到最后（在本例中是第一个）--这会产生一个小事件，索引中的一个交换，然后我们再次中断内部循环。回到循环，最后一个循环再次被递减，这次给出2，1--小事件，等等。最终整个for循环只发生了主要事件，没有次要事件——也就是说，循环开始时都是所有的，所以递减将每个循环都变为零（主要事件），最后一个循环上没有yield。

由于在该循环中没有执行过break，我们取for分支的else，它返回。注意while n可能有点误导：它实际上充当一个while True--n永远不会改变，while循环只存在于该return语句中；它同样可以表示为if not n: return后跟while True:，因为当然当n是0（空的“池”）时，在第一个之后就没有其他东西可以产生了，平凡的空yield。作者决定通过折叠if not n:检查来保存几行。

我建议你继续检查一些更具体的案例——最终你应该我能感觉到“时钟”在运转。一开始只关注cycles（可能相应地编辑print语句，从它们中删除indices），因为它们在轨道上像时钟一样的进展是这个微妙而深入的算法的关键；一旦你发现了cycles的错误，那么indices根据cycles的顺序得到正确更新的方式几乎是一种反时限！-)

Answer 2

用结果的模式来回答比用词更容易（除了你想知道理论中的数学部分）， 所以打印出来是最好的解释方式。
最微妙的是， 循环结束后，它会将自己重置为上一轮的第一轮，然后开始下一轮循环，或继续重置为上一轮的第一轮，甚至更大的一轮，如时钟。

执行重置作业的代码部分：

         if cycles[i] == 0:
             indices[i:] = indices[i+1:] + indices[i:i+1]
             cycles[i] = n - i

整体：

In [54]: 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])
    ...:     print(indices, cycles)
    ...:     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
    ...:                 print("reset------------------")
    ...:                 print(indices, cycles)
    ...:                 print("------------------")
    ...:             else:
    ...:                 j = cycles[i]
    ...:                 indices[i], indices[-j] = indices[-j], indices[i]
    ...:                 print(indices, cycles, i, n-j)
    ...:                 yield tuple(pool[i] for i in indices[:r])
    ...:                 break
    ...:         else:
    ...:             return

部分结果：

In [54]: list(','.join(i) for i in permutations('ABCDE', 3))
([0, 1, 2, 3, 4], [5, 4, 3])
([0, 1, 3, 2, 4], [5, 4, 2], 2, 3)
([0, 1, 4, 2, 3], [5, 4, 1], 2, 4)
reset------------------
([0, 1, 2, 3, 4], [5, 4, 3])
------------------
([0, 2, 1, 3, 4], [5, 3, 3], 1, 2)
([0, 2, 3, 1, 4], [5, 3, 2], 2, 3)
([0, 2, 4, 1, 3], [5, 3, 1], 2, 4)
reset------------------
([0, 2, 1, 3, 4], [5, 3, 3])
------------------
([0, 3, 1, 2, 4], [5, 2, 3], 1, 3)
([0, 3, 2, 1, 4], [5, 2, 2], 2, 3)
([0, 3, 4, 1, 2], [5, 2, 1], 2, 4)
reset------------------
([0, 3, 1, 2, 4], [5, 2, 3])
------------------
([0, 4, 1, 2, 3], [5, 1, 3], 1, 4)
([0, 4, 2, 1, 3], [5, 1, 2], 2, 3)
([0, 4, 3, 1, 2], [5, 1, 1], 2, 4)
reset------------------
([0, 4, 1, 2, 3], [5, 1, 3])
------------------
reset------------------(bigger reset)
([0, 1, 2, 3, 4], [5, 4, 3])
------------------
([1, 0, 2, 3, 4], [4, 4, 3], 0, 1)
([1, 0, 3, 2, 4], [4, 4, 2], 2, 3)
([1, 0, 4, 2, 3], [4, 4, 1], 2, 4)
reset------------------
([1, 0, 2, 3, 4], [4, 4, 3])
------------------
([1, 2, 0, 3, 4], [4, 3, 3], 1, 2)
([1, 2, 3, 0, 4], [4, 3, 2], 2, 3)
([1, 2, 4, 0, 3], [4, 3, 1], 2, 4)