python 中 `itertools.combinations` 的计算复杂度是多少？

Question

itertools.combinations in python 是查找 r 项的所有组合的强大工具，但是，我想知道它的 计算复杂性。

假设我想知道 n 和 r 的复杂度，当然它会给我所有 [= n 个术语列表中的 20=]r 个术语组合。

根据官方文档，这是粗略的实现。

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)

Answer 1

我会说它是 θ[r (n choose r)]，n choose r 部分是生成器必须 yield 的次数以及外部 while 的次数迭代。

在每次迭代中至少需要生成长度为r的输出元组，这给出了附加因子r。其他内部循环也将是每个外部迭代 O(r)。

这是假设元组生成实际上是 O(r) 并且列表 get/set 确实是 O(1) 至少平均而言给定算法中的特定访问模式。如果不是这种情况，那么仍然 Ω[r (n choose r)]。

像往常一样，在这种分析中，我假设所有整数运算都是 O(1)，即使它们的大小没有限制。

Answer 2

我也有同样的问题（For itertools.permutations）并且很难追溯其中的复杂性。这让我使用 matplotlib.pyplot 来可视化代码；

代码片段如下所示

result=[]
import matplotlib.pyplot as plt
import math
x=list(range(1,11))
def permutations(iterable, r=None): 
    count=0
    global result
    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)):
            count+=1
            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:
            resulte.append(count)
            return
for j in x:
    for i in permutations(range(j)):
        continue

x=list(range(1,11))
plt.plot(x,result)

Time Complexity graph for itertools.permutation

从图中可以看出，时间复杂度为 O(n!)，其中 n=Input Size

python 中 `itertools.combinations` 的计算复杂度是多少？

What is the computational complexity of `itertools.combinations` in python?

python

complexity-theory

time-complexity