31

有人可以解释itertools.permutationsPython 标准库 2.6 中的例程算法吗？我不明白为什么它有效。

代码是：

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
4

2 回答 2

36

您需要了解置换循环的数学理论，也称为“轨道”（了解这两个“艺术术语”很重要，因为数学学科，组合学的核心，非常先进，您可能需要查找研究可以使用其中一个或两个术语的论文）。

为了更简单地介绍排列理论，维基百科可以提供帮助。如果您对组合学足够着迷并想要进一步探索并获得真正的理解，那么我提到的每个 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]是，这意味着对索引的下一次更新是将第 i 个（从左侧）与从右侧j的第 j 个交换（例如，如果是 1，那么 的最后一个元素是换了—— ）。然后，当一个项目在其递减期间达到 0时，“批量更新”的频率就会降低：jindicesindices[-1]cycles

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

这将第ith 项indices放在最后，将索引的所有后续项向左移动一个，并表明下次我们来到第 项时，cycles我们将（从左侧）交换新的i第 th 项indices第n - 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——最后一个现在是零，所以这是一个“大”事件——索引中的“质量交换”（这里没有太多的质量，但是，可能有；-) 并且循环又回到 3、2。但是现在我们还没有中断 for 循环，所以我们继续递减下一个-to-last（在这种情况下，第一个）——它给出了一个次要事件，一个交换索引，我们再次打破内部循环。回到循环，最后一个再次递减，这次给出 2、1——次要事件等。最终，整个 for 循环发生，只有主要事件，没有次要事件——这就是循环开始为所有事件的时候，因此减量使每个都为零（主要事件），yield在最后一个周期不会发生。

由于break在该循环中从未执行过，我们采用返回的else分支for。请注意，这while n可能有点误导：它实际上充当while True--n从不更改，while循环仅从该return语句退出；它同样可以用 来表示，因为当然 when is (empty "pool") 在第一个微不足道的 emptyif not n: return之后没有什么可以让步了。作者只是决定通过折叠带有;-) 的支票来节省几行。while True:n0yieldif not n:while

我建议你继续研究一些更具体的案例——最终你应该会感觉到“发条”在运作。一开始只关注cycles（也许print相应地编辑语句，indices从它们中删除），因为它们在轨道上的发条式进展是这种微妙而深入的算法的关键；一旦你理解了这一点，indices根据顺序正确更新的方式cycles几乎是一种反高潮！-)

于 2010-04-02T15:24:45.853 回答
1

结果中的模式比文字更容易回答（除非你想知道理论的数学部分），所以打印出来是最好的解释方式。
最微妙的是，循环到最后，它会自己复位到上一圈的第一圈，然后开始下一个循环，或者不断复位到最后一圈甚至更大的圈，就像一个时钟一样.

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

         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)
于 2018-02-28T03:30:13.557 回答