Htykuut

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.