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)
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.
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
