CODEWITHSUNDEEP
pythonperformancememorycombinatorics
dougvk
dougvk

Reputation: 3734

What's the most memory efficient way to generate the combinations of a set in python?

This is the code I came up with:

def combinations(input):
    ret = ['']
    for i in range(len(input)):
        ret.extend([prefix+input[i] for prefix in ret])
    return ret

This algorithm is O(2^n) time, but can space be reduced? I heard using yield might work, but having trouble thinking through how to implement with yield. Please don't use the built in combination function -- I would like to see how it's implemented.

Upvotes: 6

Views: 2014

Answers (3)

lvc
lvc

Reputation: 35089

You can use yield in your code like so:

def combinations(input):
    ret = ['']
    yield ''
    for i in range(len(input)):
        for prefix in ret:
             combination = prefix+input[i]
             ret.extend(combination)
             yield combination

But it doesn't save you any space.

The itertools.combinations documentation shows a (much) more complicated algorithm that works in constant space - the actual implementation is in C, but claims to be equivalent.

Upvotes: 3

Mike Axiak
Mike Axiak

Reputation: 12004

Your question specifically said you wanted to see what the code would look like, so here is a hand coded example of an O(n) space solution:

def combinations(input_list, acc=''):

    if not input_list:
        yield acc
        return

    next_val = input_list[0]

    for rest in combinations(input_list[1:], acc):
        yield rest

    acc += next_val

    # In python 3.2, you can use "yield from combinations(input_list[1:], acc)"
    for rest in combinations(input_list[1:], acc):
        yield rest

Note that the substring arithmetic might be expensive (since it has to copy the string many times), so here is a slightly more efficient version in terms of complexity:

def combinations(input_list, acc='', from_idx=0):

    if len(input_list) <= from_idx:
        yield acc
        return

    next_val = input_list[from_idx]

    for rest in combinations(input_list, acc, from_idx + 1):
        yield rest

    acc += next_val

    # In python 3.2, you can use "yield from combinations(input_list[1:], acc)"
    for rest in combinations(input_list, acc, from_idx + 1):
        yield rest

I'm not using Python 3.2, but if you were you could write it like this:

def combinations(input_list, acc='', from_idx=0):

    if len(input_list) <= from_idx:
        yield acc
        return

    next_val = input_list[from_idx]

    yield from combinations(input_list, acc, from_idx + 1)
    acc += next_val
    yield from combinations(input_list, acc, from_idx + 1)

I should also note that this is purely academic since itertools.combinations does a fine job and works for a wider array of inputs (including generator expressions).

Upvotes: 6

user1277476
user1277476

Reputation: 2909

Something like this should do it:

>>> print list(itertools.combinations({1, 2, 3, 4}, 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
>>>

Upvotes: 1

Related Questions