python - Python 中列表/集合的并集

Question

我正在编写一个小函数，用于查找数字列表 S 的所有子集，输出是一个列表列表。

def subsets(S):
    if S is None or len(S) == 0:
        return [[]]

    output_list = []
    sub = [[[], [S[0]]]]
    for i in xrange(1, len(S)):
        without_ith = sub[i - 1]
        with_ith = [element + [S[i]] for element in without_ith]

        # convert to set of tuples, for set union
        without_set = set(tuple(element) for element in without_ith)
        with_set = set(tuple(element) for element in with_ith)
        new_set = without_set | with_set

        # convert back to list of lists
        new = list(list(element) for element in new_set)
        sub.append(new)

    # sort each sublist into non-descending order
    # output_list = [sorted(element) for element in sub[-1]]
    for element in sub[-1]:
        output_list.append(sorted(element))
    return output_list

该算法在这篇文章的接受答案中进行了描述:Finding all the subsets of a set

让我烦恼的是从列表列表到元组集合的转换，然后执行两组元组的并集，然后转换回列表列表。所有这些都发生在每次迭代中。原因是在Python中，集合必须包含不可变对象(immutable对象)，这些对象是可哈希的，以便与其他集合执行集合操作。但是列表和集合是可变的且不可散列的，需要元组或卡住集作为此类集合的元素。对于我的代码，我首先改变元素列表并将它们转换为并集的元组，然后转换回列表。我想知道是否有解决方法？它看起来不是很干净和高效。

(还有一个小疑问是我注释掉的列表理解 # output_list = [sorted(element) for element in sub[-1]]。我正在使用 PyCharm，它建议替换使用 for 循环进行列表理解。有什么原因吗？我认为列表理解总是更好。)

Answer 1

您的 without_ith 和 with_ith 列表之间没有重复的项目，因为前者的列表从不包含 S[i] 而那些后者总是这样做。这意味着组合它们时无需使用 set 对象，只需将一个列表连接到另一个列表即可!或者，您可以使用单个列表变量并使用列表理解扩展它:

def subsets(S):
    results = [[]]
    for x in S:
        results.extend([item + [x] for item in results])
    return results

如果您的输入列表已排序，则所有子集也将排序。如果输入并不总是按顺序排列，而您需要输出按顺序排列，请在 sorted(S) 上循环，而不是直接在 S 上循环。子集中的项目将始终按照它们迭代的顺序出现。

请注意，在 extend 调用中使用列表理解而不是生成器表达式非常重要。生成器将继续迭代新添加的项目，从而导致无限循环(直到您的系统耗尽内存来扩展列表)。