What is the most efficient memory method for creating set combinations in python?

Question

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 has O (2 ^ n) time, but can space be reduced? I heard that use yieldcan work, but I have problems with how to implement using yield. Please do not use the built-in combination function - I would like to see how it is implemented.

Answer 1

Your question specifically said that you want to see how the code will look, so here is an example of space for O (n) space:

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

, ( ), :

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

Python 3.2, , :

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)

, , itertools.combinations ( ).

Answer 2

- :

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

Answer 3

yield :

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

.

itertools.combinations () , - C, , .