What is the computational complexity of `itertools

Question

itertools.combinations in python is a powerful tool for finding all combination of r terms, however, I want to know about its computational complexity.

Let's say I want to know the complexity in terms of n and r, and certainly it will give me all the r terms combination from a list of n terms.

According to the Official document, this is the rough implementation.

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

I had this same question too and had a hard time tracing the complexities. This led me to visualize the code using matplotlib.pyplot;

The code snippet is shown below

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

From the graph, it is observed that the time complexity is O(n!) where n=Input Size

Answer 2

I would say it is θ[r (n choose r)], the n choose r part is the number of times the generator has to yield and also the number of times the outer while iterates.

In each iteration at least the output tuple of length r needs to be generated, which gives the additional factor r. The other inner loops will be O(r) per outer iteration as well.

This is assuming that the tuple generation is actually O(r) and that the list get/set are indeed O(1) at least on average given the particular access pattern in the algorithm. If this is not the case, then still Ω[r (n choose r)] though.

As usual in this kind of analysis I assumed all integer operations to be O(1) even if their size is not bounded.