问用Python计算给定集的幂集
EN

Code Review用户

提问于 2017-09-29 16:53:40

回答 1查看 5.1K关注 0票数 4

问题：

给定一个集合(例如整数)，返回其所有子集的列表(也称为幂集)。

它看起来很有用，但我希望对算法和Python编码风格和技术进行反馈，因为我对Python还很陌生。

def get_power_set(s):

    empty_set = set()
    power_set = [empty_set]

    for elem in s:
        # Need this temporary list because we can't change the power_set list while iterating it. Or so I think.
        new_sets = [] 
        for power_set_item in power_set:
            new_set = set().union(power_set_item) # Is this the best way to copy set?
            new_set.add(elem)
            new_sets.append(new_set)
        power_set.extend(new_sets)

    return power_set

combinatorics

set

python

algorithm

programming-challenge

回答 1

Code Review用户

回答已采纳

发布于 2017-09-30 04:00:16

为您的问题找到合适的数据类型。

这实际上是任务中的一个问题。根据定义，功率集是一个集合。您甚至使用变量名power_set，所以实际上它是一个列表而不是一个集合，这是非常令人惊讶的。

冗余命名：

很明显，set()是一个空集:更好的使用: power_set = [set()]

如果没有必要，不要缩写：

你可以写for element in s

姓名：

命名是最难的部分。但我将power_set_item简单地称为subset。

运算符

这是开放的辩论，也许只是我的品味，但我会使用|而不是联合方法。这也意味着使用|=和+=而不是更新和扩展。

复制

通常，复制的最佳方法是调用copy方法：new_set = power_set_item.copy()。但在您的示例中，需要注意的是，|和.union返回一个新集，以便您可以编写：

new_sets.append(subset | {element})

所有点加在一起产生以下代码：

def get_power_set(s):

    power_set = [set()]

    for element in s:
        new_sets = [] 
        for subset in power_set:
            new_sets.append(subset | {element})
        power_set.extend(new_sets)

    return power_set

清单理解：

正如您在评论中所写的，您不喜欢new_sets变量。你可以很容易地摆脱它，通过使用列表理解。一般来说，如果您有如下代码：

A = []
for j in B:
    x = do_stuff(j)
    A.add(x)

请始终检查是否无法以下列方式编写它：

A = [do_stuff(j) for j in B]

这使我们现在有了以下改进：

def get_power_set(s):

    power_set = [set()]

    for element in s:
        one_element_set = {element}
        power_set += [subset | one_element_set for subset in power_set]

    return power_set

使用one_element_set = {element}的目的是防止重复创建一个新对象的代价可能很高。

数据类型

回到第一点。如果我们使用前面的代码，我们可以很容易地修改它，返回一组frozensets：

def get_power_set(s):

    power_set = {frozenset()}

    for element in s:
        one_element_set = frozenset({element})
        power_set |= {subset | one_element_set for subset in power_set}

    return power_set