Python 中的幂集操作

Question

我正在处理一个集合，所以如果你有一个包含 n 个不同元素的集合（又名：列表），那么你就有 2^n 个子集。我在这里展示如何：

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        yield [ss for mask, ss in zip(masks, s) if i & mask]

l = list(powerset(["A", "B"]))
print(l)

给出：

[[], ['A'], ['B'], ['A', 'B']]

现在如何使用上面的列表消除空列表，并合并最后一个元素，使其成为：

['A', 'B', 'AB']

我想重复这个过程5次，获取最终输出并写入它的子列表，消除空列表并将它们落入同一个子列表的那些元素合并。

Answer 1

首先过滤掉falsy（空）元素，然后加入剩余元素的元素：

>>> l = [[], ['A'], ['B'], ['A', 'B']]
>>> list(map(''.join, filter(bool, l)))
['A', 'B', 'AB']

等效list-comprehensiony方式：

>>> l = [[], ['A'], ['B'], ['A', 'B']]
>>> [''.join(e) for e in l if e]
['A', 'B', 'AB']

做五次，做五次：

start = ["A", "B"]
for _ in range(5):
    start = [''.join(e) for e in powerset(start) if e]

Answer 2

也许您需要 flatmap 之类的东西？

from itertools import chain, imap

def flatmap(f, items):
        return chain.from_iterable(imap(f, items))

>>> list(flatmap(lambda x: x, [[], ['A'], ['B'], ['A', 'B']]))
['A', 'B', 'A', 'B']

Answer 3

这是您要找的吗：

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1 << x):
        item = ''.join([ss for mask, ss in zip(masks, s) if i & mask])
        if item:
            yield item
l = list(powerset(["A", "B", "C"]))
print(l) 
#['A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']

我介绍了 C，因为它显然适用于 A 和 B。

Answer 4

要摆脱空集，只需使用 1 而不是 0 开始循环，然后 ''.join:

def powerset(s):
    x = len(s)
    masks = [1 << i for i in range(x)]
    for i in range(1, 1 << x):
        yield ''.join(ss for mask, ss in zip(masks, s) if i & mask)

如果你想重复这个，即得到原始列表的幂集的幂集，只需将结果循环反馈给函数：

lst = ["A", "B"]
for _ in range(5):
    lst = list(powerset(lst))
    print(lst)

话虽如此，将此过滤和加入作为 post-processing 步骤可能更有意义，如@L3viathan 的回答，因为真正的 powerset 函数不应省略或修改结果.

Answer 5

data = [[], ['A'], ['B'], ['A', 'B']]
list(filter(None,map(lambda x:''.join(x) if x else None, data)))
>>>['A', 'B', 'AB']

Python 中的幂集操作

Power set manipulation in Python

python

python-3.x

list

for-loop

powerset