20
votes

I'm trying to find a way to write a combination function. Where can I find it?

3

3 Answers

25
votes

See in the documentation of itertools.combinations. There is an equivalent code for this function:

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 = 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)
38
votes

The actual source code is written in C and can be found in the file itertoolsmodule.c.

0
votes

The while loop solution may be quite confusing... I wrote an "easier-to-understand" code using recursion. For every decision we make, we need to make more decisions until the combination reaches the length we desire (base case). Following is the code for itertools.combinations but considering that permutation is just an order-sensitive version of combinations, you can remove the sorting and hashset and easily make it an itertools.permuations method.

def combinations(curr, result, used):
    if len(curr) == l:
        result.add(tuple(sorted(curr))) #Modify this line to change it into itertools.permutations
        return
    else:
        for i in arr:
            if len(curr) == 0:
                check_set = set()
            else:
                check_set = used
            if i not in used:
                temp = curr + [i]
                check_set.add(i)
                combinations(temp, result, check_set)