python - 在 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 做得很好并且适用于更广泛的输入(包括生成器表达式)。