python - python itertools.permutations的算法

有人可以解释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

最佳答案

您需要了解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的方式几乎是反高潮!-)

关于python - python itertools.permutations的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2565619/