python itertools.permutations的算法

Question

有人能解释一下Python标准库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可以提供帮助。我提到的每个URL都提供了合理的参考书目，如果您对组合学足够着迷，想要进一步探索它并获得真正的理解(我确实是这样做的--它已经成为我的一种爱好；-)。

一旦你理解了数学理论，代码对于“逆向工程”来说仍然是微妙和有趣的。显然，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

这将indices的第i项放在最末尾，将后面的所有索引项向左移动1，并表明下一次我们到达此cycles项时，我们将交换新的i第indices项(从左)与n - i第1项(从右)-这将再次是i第1项，当然，除了将有一个

cycles[i] -= 1

在我们下一步研究它之前；-)。

当然，最困难的部分是向证明这是可行的--也就是说，所有的排列都是详尽生成的，没有重叠，并且有一个正确的“定时”退出。我认为，与证明相比，在简单的情况下查看机制是如何工作的可能更容易一些--注释掉yield语句并添加print语句(Python2.*)，我们有

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循环只发生主要事件，没有次要事件--也就是说，当循环开始时都是1，所以递减使每个循环都为0(主要事件)，在最后一个周期中没有yield发生。

由于在该周期中从未执行过break，因此我们采用for的else分支，该分支返回。注意，池可能有点误导:它实际上充当了一个池--代码永远不变，while循环只存在于该return语句中；它同样可以表示为if not n: return，后跟while True:，因为当n为0 (空“0”)时，在第一个微不足道的空<代码>d46之后就没有什么可产生的了。作者刚刚决定通过使用while;-)折叠if not n:检查来节省几行代码。

我建议您继续研究一些更具体的案例--最终您应该会了解到“发条”的操作。首先只关注cycles (可能会相应地编辑print语句，删除其中的indices )，因为它们在轨道上的精确运行是这种微妙而深入的算法的关键；一旦您摸索到了这一点，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)