Python中的Powerset with frozenset

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

如果我用以下命令运行程序：

    print(powerset3(set(['a', 'b'])))

我得到了以下解决方案

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

但是我想要

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

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

谢谢你的帮忙

Answer 1

这是一个使用itertools的可读性稍高的实现，如果你不想使用库来表示组合，可以用它的实现替换组合代码，例如来自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上进行测试

In [82]: powerset(['a', 'b'])
Out[82]:
frozenset({frozenset(),
           frozenset({'b'}),
           frozenset({'a'}),
           frozenset({'a', 'b'})})

In [83]: powerset(['x', 'y', 'z'])
Out[83]:
frozenset({frozenset(),
           frozenset({'x'}),
           frozenset({'x', 'z'}),
           frozenset({'y'}),
           frozenset({'x', 'y'}),
           frozenset({'z'}),
           frozenset({'y', 'z'}),
           frozenset({'x', 'y', 'z'})})

In [84]: powerset([])
Out[84]: frozenset({frozenset()})

Answer 2

你的想法是对的。如果a不为空，那么a的powerset可以通过从a中提取一些元素s来形成，我们将其称为剩余的rest。然后从rest的powerset构建s的powerset，方法是为powerset3(rest)中的每个subset添加subset本身和subset | frozenset({s})。

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

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

这是一个可行的解决方案：

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))