在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。请不要使用内置的组合函数——我想看看它是如何实现的。

- dougvk

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

- Mike Axiak

Answer 2

您可以在代码中使用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 语言编写的，但声称等效。请参考实际实现代码。

- lvc

Answer 3

大概像这样就可以了：

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

- user1277476

---

-1，因为问题要求不仅使用 itertools.combinations。 - lvc

以上是一项昂贵的操作。列表转换需要大量的内存。 - Pramit