Python中带frozenset的Powerset

Question

我在这里坐了将近5个小时试图解决这个问题，现在我希望得到你的帮助。在

下面是我的Python代码：

   def powerset3(a):

       if (len(a) == 0):
           return frozenset({})
       else:
           s=a.pop()
           b=frozenset({})
           b|=frozenset({})
           b|=frozenset({s})
           for subset in powerset3(a):

              b|=frozenset({str(subset)})
              b|=frozenset({s+subset})
           return b

如果我运行程序：

^{pr2}$

我得到以下解决方案

    frozenset({'a', 'b', 'ab'})

但我想

    {frozenset(), frozenset({'a'}), frozenset({'b'}), frozenset({'b', 'a'})}

我不想使用库，它应该是递归的！在

谢谢你的帮助

Answer 1

下面是一个使用itertools的更可读的实现，如果您不想为组合使用lib，可以用它的实现替换组合代码，例如从https://docs.python.org/2/library/itertools.html#itertools.combinations

def powerset(l):
    result = [()]
    for i in range(len(l)):
        result += itertools.combinations(l, i+1)
    return frozenset([frozenset(x) for x in result])

使用不同长度的IPython测试

^{pr2}$

Answer 2

你的想法是对的。如果a是非空的，那么a的功率集可以通过从a获取一些元素s来形成，我们称之为rest。然后从rest的powerset中构建s的powerset，方法是对powerset3(rest)中的每个subset本身和subset | frozenset({s})进行相加。在

最后一点，使用subset | frozenset({s})而不是字符串连接，这是解决方案缺少的一半。另一个问题是基本情况。元素集的集合不是空的。在

解决方案的另一个问题是，您试图以可变的方式使用frozenset，它是不可变的（例如pop()，b |= something，等等）

这里有一个可行的解决方案：

from functools import partial

def helper(x, accum, subset):
    return accum | frozenset({subset}) | frozenset({frozenset({x}) | subset})

def powerset(xs):
    if len(xs) == 0:
        return frozenset({frozenset({})})
    else:
        # this loop is the only way to access elements in frozenset, notice
        # it always returns out of the first iteration
        for x in xs:
            return reduce(partial(helper, x), powerset(xs - frozenset({x})), frozenset({}))        

a = frozenset({'a', 'b'})
print(powerset(a))