在python中生成集合组合的最有效内存方法是什么？

Question

这是我提出的代码:

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

这个算法是O(2 ^ n)时间,但可以减少空间吗？我听说使用yield可能有用,但无法思考如何实现yield.请不要使用内置组合功能 - 我想看看它是如何实现的.

Answer 1

你的问题明确表示你想看看代码会是什么样子,所以这里是一个O(n)空间解决方案的手工编码示例:

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它做得很好,适用于更广泛的输入(包括生成器表达式).