Python itertools 模块中的全排列算法，看起来简单却非常让人费解!

[lxy42]

在刷 leetcode 时遇到了全排列问题，想来想去也只能想出递归的解法。然后突然想起 Python 的 itertools 模块中有全排列的函数，模块源码是用 C 写的，不过在官方文档中有提供 Python 版本的代码，代码看起来非常简单，但是我看了很久都看不懂算法的原理是什么。

接着在 SO 上发现了相关问题，根据“ Alex Martelli ”的回答，该算法涉及到了Cyclic permutation 理论。有兴趣的同学可以研究一下代码和 Cyclic permutation 理论。

附上代码

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 = list(range(n))
    cycles = list(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

[bomb77]

谢谢分享，学习了

[jameslan]

C++也有啊

[glasslion]

stl 也一样， 全排列的标准算法

[lxy42]

@jameslan @glasslion 好像网上讨论这个算法的人比较少，我看了大都是递归和字典序算法

[Philippa]

做缓存时蛮方便的

[gnaggnoyil]

NOIP2004 普及组最后一题.我以为已经是常识了……

[locktionc]

我一般用的是二进制来做的。
A->1000
B->0100
C->0010
D->0001

例如
0110 对应了 BC
1011 对应了 A CD

所以只要计算 1 （ 0001 ）到 15 （ 1111 ）就可以得到所有组合

[genesislive]

@locktionc 4 个字母的全排列不是有 24 种情况吗？计算 1-15 怎么得到所有组合？

[locktionc]

@genesislive 我说的是一个类似的题的做法，全排列因此稍稍改一下。

[wizardoz]

@genesislive 他算出的是组合，题主问的是排列

[wizardoz]

@locktionc 受教了！ 9 年前大学毕业面试题就做过这题，我一直以为我的解法是对的，今天看到你的答案比我的好多了！