python - python itertools.permutations 的算法

Question

有人可以解释itertools.permutations的算法吗？ Python 标准库 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

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

这把 i indices 第一项最后，将所有后面的索引项向左移一位，表示下次我们来到 cycles的这一项我们将更换新的 i 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 循环，所以我们继续递减倒数第二个(在这种情况下，第一个)- - 这给出了一个小事件，索引中的一次交换，我们再次打破了内部循环。回到循环，再一次递减最后一个，这次给出 2, 1 - 次要事件等。最终整个 for 循环只发生主要事件，没有次要事件 - 那是循环开始时所有事件，所以减量将每个都归零(主要事件)，没有 yield发生在最后一个周期。

由于没有 break在那个循环中执行过，我们取 else for的分支，返回。请注意 while n可能有点误导:它实际上充当 while True -- n永不改变， while循环仅从 return 退出陈述;它同样可以表示为 if not n: return其次是 while True: , 因为当然当 n是 0 (空“池”)在第一个微不足道的空之后没有什么可以产生的 yield .作者只是决定通过折叠 if not n: 来保存几行请联系 while ;-)

我建议你继续研究一些更具体的案例——最终你应该能感觉到“发条”在运行。专注只是 cycles起初(可能相应地编辑 print 语句，从它们中删除 indices)，因为它们在轨道上的发条般的进展是这种微妙而深刻的算法的关键；一旦你理解了，方式 indices正确更新以响应 cycles 的顺序几乎是一个反高潮!-)