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

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)

Solution

I had this same question too (For itertools.permutations) 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

Comments

[kaya3]

The time complexity is not O(n!); it should be O(n! * n). Plotting a graph can't tell you the time complexity; it can only give you clues.