解释Python模块itertools的组合函数
我经常在Python中使用itertools模块，但如果我不知道它背后的逻辑，就觉得有点像是在作弊。
这里有一段代码，用来找出字符串的组合，当顺序不重要的时候。
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
有人能帮我解释一下基本思路吗？特别是第14行。
3 个回答
2
注意！代码在这里会被拆分，格式也不会和它的各个部分保持正确的缩进，所以我建议你去看看问题中的代码或itertools文档（代码是一样的）。
这个问题已经被问了超过7年，真是久远啊。我自己也对这个问题感兴趣，虽然上面的解释很有帮助，但对我来说还是没完全明白，所以我总结了一个我自己的版本。
现在我终于搞明白了（或者我觉得我明白了），我想把这个“版本”的解释分享出来，可能会对和我一样的人有帮助。那我们开始吧。
def combinations(iterable, r):
pool = tuple(iterable)
n = len(pool)
在第一部分，简单地把可迭代对象变成一个元组，并获取这个可迭代对象的长度。这些信息后面会用到。
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
这一部分也很简单——如果我们需要的组合长度大于我们可用的元素数量，那就无法构造出有效的组合（比如说，你不能从4个元素中组合出5个），所以我们直接用return语句停止执行。同时，我们还生成了第一个组合（从可迭代对象中取前r个元素）。
接下来的部分稍微复杂一点，所以要仔细读。
while True:
for i in reversed(range(r)):
if indices[i] != n - (r - i):
break
"""
The job of the while loop is to increment the indices one after
the other, and print out all the possible element combinations based
off all the possible valid indice combinations.
This for loop's job is to make sure we never over-increment any values.
In order for us to not run into any errors, the incremention of
the last element of the indice list must stop when it reaches one-less
than the length of our element list, otherwise we'll run into an index error
(trying to access an indice out of the list range).
How do we do that?
The range function will give us values cascading down from r-1 to 0
(r-1, r-2, r-3, ... , 0)
So first and foremost, the (r-1)st indice must not be greater than (n-1)
(remember, n is the length of our element pool), as that is the largest indice.
We can then write
Indices[r - 1] < n - 1
Moreover, because we'll stop incrementing the r-1st indice when we reach it's
maximum value, we must also stop incrementing the (r-2)nd indice when we reach
it's maximum value. What's the (r-2)nd indice maximum value?
Since we'll also be incrementing the (r-1)st indice based on the
(r-2)nd indice, and because the maximum value of the (r-1)st
indice is (n-1), plus we want no duplicates, the maximum value the
(r-2)nd indice can reach would be (n-2).
This trend will continue. more generally:
Indices[r - k] < n - k
Now, since r - k is an arbitrary index generated by the reversed range function,
namely (i), we can substitute:
r - k = i -----> k = r - i
Indices[r - k] < n - k -----> Indices[i] < n - (r - i)
That's our limit - for any indice i we generate, we must break the
increment if this inequality { Indices[i] < n - (r - i) } is no longer
true.
(In the documentation it's written as (Indice[i] != i + n - r), and it
means the exact same thing. I simply find this version easier to visualize
and understand).
"""
else:
return
"""
When our for loop runs out - which means we've gone through and
maximized each element in our indice list - we've gone through every
single combination, and we can exit the function.
It's important to distinct that the else statement is not linked to
the if statement in this case, but rather to the for loop. It's a
for-else statement, meaning "If you've finished iterating through the
entire loop, execute the else statement".
"""
如果我们成功跳出了for循环，这意味着我们可以安全地增加我们的索引，以获取下一个组合（下面的第一行）。下面的for循环确保每次我们在新的索引上开始时，都会把其他索引重置到最小值，这样就不会漏掉任何组合。
举个例子，如果我们不这样做，一旦我们到达一个需要移动的点，比如我们有(0, 1, 2, 3, 4)，而组合索引是(0, 1, 4)，当我们移动并把1增加到2时，最后一个索引仍然是4，这样我们就会错过(0, 2, 3)，只会记录(0, 2, 4)作为有效组合。相反，在我们增加(1 -> 2)后，我们会根据这个更新后面的索引：(4 -> 3)，当我们再次运行while循环时，我们会把3增加回4（参考前面的部分）。
注意，我们从来不增加之前的索引，以避免产生重复的组合。
最后，在每次迭代中，yield语句会生成与当前索引组合对应的元素组合。
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
正如文档所说，因为我们处理的是位置，所以一个独特的组合是基于元素在可迭代对象中的位置，而不是它们的值。
4
在编程中，有时候我们会遇到一些问题，比如代码运行不正常或者出现错误。这时候，我们可以去一些技术论坛，比如StackOverflow，寻求帮助。在这些论坛上，很多人会分享他们的经验和解决方案。
例如，有人可能会描述他们遇到的具体问题，提供一些相关的代码片段，像是
def combinations(iterable, r):
# first, we need to understand, this function is to record every possibility of indices
# then return the elements with the indices
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
# yield the first permutation,
# cause in the "while" circle, we will start to change the indices by plus 1 consistently
# for example: iterable is [1, 2, 3, 4, 5], and r = 3
# this yield will return [1, 2, 3], but in the "while" loop,
# we will start to update last elements' index to 4, which will return [1, 2, 4]
yield tuple(pool[i] for i in indices)
while True:
# in this for loop, we want to confirm whether indices[i] can be increased or not
for i in reversed(range(r)):
# after reversed, i will be r-1, r-2, r-3, ....,0
# something we should know before we start the 'for' loop
# the value of indices[r-1] should not greater than n-1
# the value of indices[r-2] should not greater than n-2
# and the maximum of indices[i] should be indices[r-1]
# so the value of indices[r-1] should between r-1 and n-r + r-1, like this:
# r-1 <= indics[r-1] <= n-r + r-1
# so, to r-2:
# r-2 <= indics[r-1] <= n-r + r-2
# let's set i = r-1:
# i <= indices[i] <= n-r+i (n-1 is the maximum value)
# since we will keep plusing the value of indices[i], let's ignore i <= indices[i]
# and we just want to know if indices[i] can plus or not,
# so indices[i] can be equal with n-r+i
# then we got:
# indices[i] < i + n - r
# the offical document give: indices[i] != i + n - r,
# cause when indices[i] == i + n - r, it arrived the boundry,
# the "for" loop will get into indices[i-1], there will be no judgement for ">i+n-r"
# so to use indices[i] != i + n - r is still a good way,
# but i prefer indices[i] < i + n - r, which is easier to understand for me.
# so next question is "break" in here,
# it means the value of indices[i] doesn't reach the boundry still can plus one,
# let break out to continue the iteration
# when it hit the boundry, i will be r-2
# So we can see the result:
# 1, 2, 3
# 1, 2, 4
# 1, 2, 5
# 1, 3, 4
# always loop the last index, hit the boundry, check the last but one.
if indices[i] < i + n - r:
break
else:
# loop finished, return
return
# first of all, plus one for current indices[i],
# that's why we yield the first permutation, before the while loop
# and increase every indices[i] by 1
indices[i] = indices[i] + 1
# this for loop is increase every indices which is after indices[i].
# cause, current index increased, and we need to confirm every one behind is orderd
# for example: current we got i = 2, indices[i]+1 will be 3,
# so the next loop will start with [1, 3, 4], not [1, 3, 3]
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
总之，技术论坛是一个很好的地方，可以让我们向其他程序员请教问题，分享经验，提升自己的编程技能。
6
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
# first you create a tuple of the original input which you can refer later with
# the corresponding indices
n = len(pool)
# get the length of the tuple
if r > n:
return
# if the length of the desired permutation is higher than the length of the tuple
# it is not possible to create permutations so return without doing something
indices = list(range(r))
# create the first list of indices in normal order ( indices = [0,1,2,3,...,r])
# up to the desired range r
yield tuple(pool[i] for i in indices)
# return the first permutation which is a tuple of the input with the original
# indices up to r tuple(tuple[0], tuple[1],....,tuple[r])
while True:
for i in reversed(range(r)):
# i will go from r-1, r-2, r-3, ....,0
if indices[i] != i + n - r:
# if condition is true except for the case
# that at the position i in the tuple the last possible
# character appears then it is equal and proceed with the character
# before which means that this character is replaced by the next
# possible one
# example: tuple='ABCDE' so n = 5, r=3 indices is [0,1,2] at start i=2
# yield (A,B,C)
# indices[i] is 2 and checks if 2 != 4 (2 +5-3) is true and break
# increase indices[i]+1 and yield (A,B,D)
# indices[i] is 3 and checks if 3 != 4 (2 +5-3) is true and break
# increase indices[i]+1 and yield (A,B,E)
# indices[i] is 4 and checks if 4 != 4 (2 +5-3) is false so next loop
# iteration: i = 1 indices[i] is 1 and checks if 4 != 3 (1 +5-3)
# is true and break .... and so on
break
else:
# when the forloop completely finished then all possible character
# combinations are processed and the function ends
return
indices[i] += 1 # as written proceed with the next character which means the
# index at i is increased
for j in range(i+1, r):
indices[j] = indices[j-1] + 1 # all the following indexes are increased as
# well since we only want to at following
# characters and not at previous one or the
# same which is index at indice[i]
yield tuple(pool[i] for i in indices)
# return the new tuple
这段代码的意思是……
首先，它定义了一个变量，这个变量就像一个盒子，用来存放某些信息。接着，它可能会进行一些操作，比如计算、比较或者改变这个变量的值。
然后，代码中可能会有一些条件判断，就像是在问“如果这个条件成立，我该做什么？”这样可以让程序根据不同的情况做出不同的反应。
最后，代码可能会输出一些结果，告诉我们程序运行的结果是什么。总之，这段代码的目的是为了完成某个特定的任务。
希望这个解释能帮助你理解这段代码的基本意思！