python itertools.permutations的算法

Question

有人可以itertools.permutations在Python标准的lib 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

你需要理解置换周期的数学理论,也称为"轨道"(因为数学学科,组合学的核心,它是非常先进的,因此知道两个"艺术术语"很重要,你可能需要查阅研究论文可能使用一个或两个方面).

为了更简单地介绍排列理论,维基百科可以提供帮助.我提到的每个网址都提供了合理的参考书目,如果你对组合学足够了解,想要进一步探索它并获得真正的理解(我个人做过 - 这对我来说有点嗜好;-).

一旦理解了数学理论,代码对于"逆向工程"来说仍然是微妙而有趣的.显然,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 -最后还不是零却又如此,我们有一个"小"事件(在索引一个是swap),打破内循环.然后我们再次输入它,这次最后一次给出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几乎是一个反复无常的! - )