python itertools.permutations的算法
有人可以解释itertools.permutationsPython标准库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
回答：
您需要了解置换循环的数学理论，也称为“轨道”（了解两个“艺术术语”很重要，因为数学学科是组合学的核心，并且相当先进，您可能需要进行研究）论文可能使用一个或两个方面）。
对于排列理论的简单介绍，维基百科可以提供帮助。如果您对组合语言非常着迷，希望对它进行进一步的探索并获得真正的理解，我提到的每个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
这会将第ith个项目indices放在最后，将所有随后的索引项目向左移动一个，并表示下次我们来到该项目时，cycles我们将i与indices（从左边）交换新的第th个项目第三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循环，因此我们通过减少 下一个 继续
__-to-last（在本例中为第一个）-这将产生一个次要事件，在索引中进行一次交换，然后我们再次中断内部循环。
回到循环，最后一个递减，再次给出2，1-次要事件，等等。最终，整个for循环只发生主要事件，没有次要事件-
那就是当循环全部开始时，因此递减会将每个值减为零（主要事件），yield在最后一个周期中不会发生任何事情。
由于break该周期中没有执行过，因此我们将返回的else分支for。注意，这while n可能有点误导：它实际上起着while
True- n永不改变的作用，while循环仅从该return语句退出；它也可以表示为if not n:
return跟在后面while True:，因为当然，当nis 0（空“
pool”）时，在第一个琐碎的empty之后没有其他东西可产生了yield。作者只是决定通过将if not n:支票与while;-)
折叠来节省几行。
我建议您继续研究一些更具体的情况-
最终您应该了解“发条”的运行情况。首先要集中精力cycles（也许可以相应地编辑print语句，然后indices从语句中删除语句），因为它们像发条一样在轨道上的前进是这种微妙而深入的算法的关键。一旦您了解了
这一点 ，就indices可以正确地响应序列的更新方式，cycles几乎是一种反高潮！-）
以上是 python itertools.permutations的算法 的全部内容， 来源链接： utcz.com/qa/425180.html
