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

- zaharpopov

---

我可以建议观看 mCoding 的 YouTube 视频。视频的要点是，构建自己的迭代解决方案并找到与给定代码的相似之处可能比直接逆向工程给定代码更容易。 - Benjamin Wang

Answer 1

你需要了解置换循环的数学理论，也称为“轨道”（知道这两个“术语”很重要，因为数学学科——组合数学的核心相当高级，你可能需要查找使用任一或两个术语的研究论文）。

对于置换理论的简单介绍，维基百科可以提供帮助。我提到的每个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个项目放在最后，将所有后续的indices项目向左移动一个位置，并指示下次我们来到cycles的此项时，我们将用从左边开始的新的ith项目与从右边开始的第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—最后一个现在为零，所以这是一个“大”的事件—在索引中进行“大规模交换”（嗯，这里没有多少大规模，但是可能会有;-）并且这些{{cycles}}又回到了3、2。但现在我们没有打破for循环，所以我们继续通过递减下一个-to-last（在这种情况下，第一个）—这给出了一个小事件，在索引中交换一次，并再次打破内循环。回到循环，再次递减最后一个，这次是2、1—小事件等等。最终，只有主要事件而没有小事件发生整个for循环—那时这些{{cycles}}都从1开始，所以递减将每个{{cycle}}都变为零（主要事件），在最后一个{{cycle}}上不会发生yield。

由于在该循环中没有任何一个`break`被执行，我们进入了`else`分支，并返回结果。请注意，`while n`可能有点令人误解：它实际上作为`while True`-- `n`永远不会改变，只有通过那个`return`语句才能退出`while`循环；它同样可以表示为`if not n: return`，后面跟着`while True:`，因为当`n`是0（空“pool”）时，在第一个微不足道的空`yield`之后就没有更多可生成的内容了。作者决定通过将`if not n:`检查与`while`合并来节省几行代码。）

我建议您继续检查一些更具体的情况--最终您应该能够感知到“钟表”的运转。首先专注于`cycles`（也许相应地编辑`print`语句，从中删除`indices`），因为它们通过轨道的类似于时钟的进展是这种微妙而深刻的算法的关键；一旦您理解了这一点，`indices`如何根据`cycles`的排序得到适当更新的方式几乎是一个反高潮！-）

- Alex Martelli

---

我刚开始有点失望，但是总能依靠Alex！虽然我还没有完全理解这个，但你给的线索非常好，我会去了解一下。非常感谢。另外，你知道是谁在Python库中实现了这个吗？ - zaharpopov

Raymond Hettinger：请参见http://svn.python.org/view/python/trunk/Modules/itertoolsmodule.c?annotate=76602的2495行及其后续行。 - Alex Martelli

循环列表代表什么？作为一个学习了6个学期抽象代数并且对称群和循环/轨道有相当了解的人，这种符号（和代码）对我来说几乎毫无意义。我无法确定实际的一般策略是什么。 - Johnny Apple

上面的链接已经失效，请查看这里。 - That1Guy

Answer 2

我最近在重新实现排列算法的过程中遇到了同样的问题，并想分享一下我对这个有趣算法的理解。

TL;DR: 这个算法基于递归排列生成算法（基于回溯并利用交换元素），并被转化（或优化）为迭代形式。（可能是为了提高效率和防止堆栈溢出）

基础知识

在开始之前，我必须确保我们使用与原始算法相同的符号。

• n 指可迭代对象的长度
• r 指一个输出排列元组的长度

并分享一个简单的观察（如 Alex 所讨论的）：

• 每当算法 yield 一个输出时，它只取 indices 列表的前 r 个元素。

cycles

首先，让我们讨论变量 cycles 并建立一些直觉。通过一些调试打印，我们可以看到 cycles 的作用就像倒计时（时间或时钟，类似于 01:00:00 -> 00:59:59 -> 00:59:58）：

• 每个元素都初始化为 range(n, n-r, -1)，导致 cycles[0]=n，cycles[1]=n-1...cycles[i]=n-i
• 通常，只有最后一个元素会减少，并且每次减少（在减少之后给出 cycles[r-1] !=0）会产生一个输出（排列元组）。我们可以直观地将这种情况称为 tick。
• 每当一个元素（假设是 cycles[i]）减少到 0 时，它会触发前面的元素减少（cycles[i-1]）。然后触发元素（cycles[i]）被恢复到其初始值（n-i）。这种行为类似于借位减法，或者当秒数倒计时到 0 时，分钟重置为 0。我们可以直观地将这个分支命名为 reset。

为了进一步确认我们的直觉，可以向算法添加一些打印语句，并使用参数 iterable="ABCD", r=2 运行它。我们可以看到 cycles 变量的以下更改。请注意，方括号表示发生“tick”，产生输出，大括号表示发生“reset”，不产生输出。

[4,3] -> [4,2] -> [4,1] -> {4,0} -> {4,3} -> 
[3,3] -> [3,2] -> [3,1] -> {3,0} -> {3,3} -> 
[2,3] -> [2,2] -> [2,1] -> {2,0} -> {2,3} -> 
[1,3] -> [1,2] -> [1,1] -> {1,0} -> {1,3} -> {0,3} -> {4,3}

使用cycles的初始值和变化模式，我们可以得出cycles的可能解释：每个索引处剩余排列（输出）的数量。当初始化时，cycles[0]=n表示在索引0处最初有n种可能选择，cycles[1]=n-1表示在索引1处最初有n-1种可能选择，一直到cycles[r-1]=n-r+1。这种对cycles的解释与数学相符，因为通过一些简单的组合数学计算，我们可以确认这确实是这种情况。另一个支持证据是，无论何时算法结束，我们都有P(n,r)(P(n,r)=n*(n-1)*...*(n-r+1))个滴答声（在进入while之前计算初始yield为一个tick）。

indices

现在我们来到更复杂的部分，indices列表。由于这本质上是一个递归算法（更精确地说是回溯），我想从一个子问题（i=r-1）开始：当indices中从索引0到索引r-2（包括）的值固定时，只有索引r-1（换句话说，indices中的最后一个元素）的值在变化。此外，我将介绍一个具体的示例（iterable="ABCDE", r=3），我们将重点关注它如何生成前3个输出：ABC，ABD，ABE。

在解决子问题时，我们将indices列表分成3个部分，并给它们命名：

• 固定的：indices[0:r-2]（包含）
• 变化的：indices[r-1]（仅一个值）
• 积压的：indices[r:n-1]（除前两个部分外的其余部分）

由于这是一种回溯算法，我们需要在执行前后保持不变。不变量是

• 子列表包含变化和积压部分（indices[r-1:n-1]），在执行期间被修改但在结束时恢复。

现在我们可以转向while循环期间cycles和indices之间的交互。其中一些操作已经由Alex概述，我进一步阐述。

• 在每个tick中，将变化部分中的元素与积压部分中的某些元素交换，并保持积压部分中的相对顺序。
  • 使用字符可视化indices，花括号突出显示积压部分：
  • ABC{DE} -> ABD{CE} -> ABE{CD}
• 当发生reset时，将变化部分中的元素移动到积压部分的末尾，从而恢复子列表的初始布局（包含变化部分和积压部分）
  • 使用字符可视化indices，花括号突出显示变化部分：
  • AB{E}CD -> ABCD{E}

在此执行期间（i=r-1），只有tick阶段可以产生输出，并且总共产生n-r+1个输出，与cycles[i]的初始值相匹配。这也是由于数学上我们只能在固定部分固定时有n-r+1个排列选择。 在cycles[i]减少为0后，reset阶段开始工作，将cycles[i]重置为n-r+1并恢复不变量子列表。此阶段标志着此执行的结束，并表示已输出给定固定前缀部分的所有可能排列选择。 因此，我们已经证明，在这个子问题（i=r-1）中，这个算法确实是一个有效的回溯算法，因为它

• 输出给定前提条件（固定前缀部分）下的所有可能值
• 保持不变量未修改（在reset阶段中恢复）

此证明还可以推广到其他值的i，从而证明这个排列生成算法的正确性。

重新实现

哇！这是一篇很长的阅读，您可能需要更多的尝试（更多print）来完全相信算法。本质上，我们可以将算法的基本原理简化为以下伪代码：

// precondition: the fixed part (or prefix) is fixed
OUTPUT initial_permutation // also invokes the next level
WHILE remaining_permutation_count > 0
    // tick
    swap the changing element with an element in backlog
    OUTPUT current_permutation // also invokes the next level
// reset
move the changing element behind the backlog

这里有一个使用简单回溯法的Python实现：

# helpers
def swap(list, i, j):
    list[i], list[j] = list[j], list[i]

def move_to_last(list, i):
    list[i:] = list[i+1:] + [list[i]]

def print_first_n_element(list, n):
    print("".join(list[:n]))

# backtracking dfs
def permutations(list, r, changing_index):
    if changing_index == r:
        # we've reached the deepest level
        print_first_n_element(list, r)
        return
    
    # a pseudo `tick`
    # process initial permutation
    # which is just doing nothing (using the initial value)
    permutations(list, r, changing_index + 1)

    # note: initial permutaion has been outputed, thus the minus 1
    remaining_choices = len(list) - 1 - changing_index
    # for (i=1;i<=remaining_choices;i++)
    for i in range(1, remaining_choices+1):
        # `tick` phases
        
        # make one swap
        swap_idx = changing_index + i
        swap(list, changing_index, swap_idx)
        # finished one move at current level, now go deeper
        permutations(list, r, changing_index + 1)
    
    # `reset` phase
    move_to_last(list, changing_index)

# wrapper
def permutations_wrapper(list, r):
    permutations(list, r, 0)

# main
if __name__ == "__main__":
    my_list = ["A", "B", "C", "D"]
    permutations_wrapper(my_list, 2)

现在剩下的所有步骤就是展示回溯版本与itertools源代码中的迭代版本等效。一旦你理解了为什么这个算法有效，这应该相当容易。遵循各种计算机科学教材的优良传统，这留给读者自己练习。

- Nekonull

Answer 3

如果你想了解理论的数学部分，那么用结果模式回答比用文字更容易，因此打印输出是最好的解释方式。
最微妙的事情是，在循环到结尾后，它会重置为上一个轮回的第一次转动，并开始下一个循环，或者不断重置为上一个甚至更大的轮回的第一次转动，就像时钟一样。

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

         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)

- patpat