获取一个列表的列表的幂集。

Question

我被给予一个列表的列表 s:

s = [["a1", "A"], ["b4", "B"], ["a3", "A"], ["d6", "D"], ["c4", "C"]]

（注意，列表中的元素不一定以相同字母开头。为方便起见，我在此修改了数据。）

我的目标是按其第二个元素将每个列表排序到一个类别，并通过在每个类别中选择最多一个元素来获取所有可能的组合。

我首先将列表的列表哈希到一个字典中：

dic = {i[1]: [] for i in s}
for i in s:
    # set the value of the first item key to the second item
    dic[i[1]].append(i[0])

dic
>>> {'A': ['a1', 'a3'], 'B': ['b4'], 'C': ['c4'], 'D': ['d6']}

所有可能的组合数，也就是集合 s 的幂集的长度应该返回 23:

{'a1'},
{'a3'},
{'b4'},
{'c4'}, 
{'d6'}, 
{'a1', 'b4'}, 
{'a1', 'c4'}, 
{'a1', 'd6'}, 
{'a3', 'b4'}, 
{'a3', 'c4'}, 
{'a3', 'd6'}, 
{'b4', 'c4'}, 
{'b4', 'd6'}, 
{'c4', 'd6'}, 
{'a1', 'b4', 'c4'}, 
{'a1', 'b4', 'd6'}, 
{'a1', 'c4', 'd6'}, 
{'a3', 'b4', 'c4'}, 
{'a3', 'b4', 'd6'}, 
{'a3', 'c4', 'd6'}, 
{'b4', 'c4', 'd6'}, 
{'a1', 'b4', 'c4', 'd6'}, 
{'a3', 'b4', 'c4', 'd6'}

我最初想要使用多个 for 循环，但是因为我无法保证我的 s 中会有多少个 key （这也会将我的时间复杂度提高到 O(N^x)），所以我使用了 itertools.chain 和 itertools.combinations，参考了这篇文章：

def powerset(s:list):
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))

问题在于这种方法只考虑单个列表中的元素，忽略了约束条件：“最多只能从每个列表中取一个元素”。将列表扁平化将忽略分类，因此我没有尝试这样做。

欢迎提供任何解决此问题的见解。

- jstaxlin

---

为什么你的期望输出不包括“{}”？这通常被认为是幂集或笛卡尔积的一部分。 - Karl Knechtel

请参见 https://dev59.com/HHRB5IYBdhLWcg3wuZfo （我重新打开了；这不足以成为重复，而且你得到的答案展示了一个关键且不明显的技巧。） - Karl Knechtel

Answer 1

@don'ttalkjustcode的回答是可行的，但是不必要地增加了虚拟值的开销，并且还会产生一个空集合，这并不符合问题的要求。更直接的方法是使用itertools.combinations从列表字典中选择列表，然后传递给itertools.product以生成所需的组合。

from itertools import product, combinations

print(*(
    set(p)
    for r in range(len(dic))
    for c in combinations(dic.values(), r + 1)
    for p in product(*c)
), sep='\n')

这将输出：

{'a1'}
{'a3'}
{'b4'}
{'c4'}
{'d6'}
{'a1', 'b4'}
{'a3', 'b4'}
{'a1', 'c4'}
{'a3', 'c4'}
{'d6', 'a1'}
{'d6', 'a3'}
{'c4', 'b4'}
{'d6', 'b4'}
{'d6', 'c4'}
{'a1', 'c4', 'b4'}
{'a3', 'c4', 'b4'}
{'d6', 'a1', 'b4'}
{'d6', 'a3', 'b4'}
{'d6', 'a1', 'c4'}
{'d6', 'a3', 'c4'}
{'d6', 'c4', 'b4'}
{'d6', 'a1', 'c4', 'b4'}
{'d6', 'a3', 'c4', 'b4'}

- blhsing

Answer 2

您可以将类别列表，例如['a1', 'a3']转换为如下列表：[[], ['a1'], ['a3']]，对这些列表进行乘积运算，然后链接每个乘积(在线尝试！)。

from itertools import product, chain

dic = {'A': ['a1', 'a3'], 'B': ['b4'], 'C': ['c4'], 'D': ['d6']}
for p in product(*([[]] + [[s] for s in v] for v in dic.values())):
    print({*chain(*p)})

或者，给每个类别添加一个特殊的“skip”值，并将其过滤掉 (在线试用)。

from itertools import product, chain

skip = object()

dic = {'A': ['a1', 'a3'], 'B': ['b4'], 'C': ['c4'], 'D': ['d6']}
for p in product(*([skip] + v for v in dic.values())):
    print(set(p) - {skip})

嗯，我从你已经处理好的 dic 开始，因为你做得很好，但是...如果你直接从 dic = {i[1]: [skip] for i in s} 开始，那么你就不需要后来再添加它了，可以直接这样做(在线试一下！)：

for p in product(*dic.values()):
    print(set(p) - {skip})

对于第一个，同样可以通过(在线尝试!)来实现：

for p in product(*dic.values()):
    print({*chain(*p)})

所有输出结果（由于字符串哈希随机化，后两个可能显示不同的顺序）：

set()
{'d6'}
{'c4'}
{'d6', 'c4'}
{'b4'}
{'d6', 'b4'}
{'b4', 'c4'}
{'d6', 'b4', 'c4'}
{'a1'}
{'d6', 'a1'}
{'a1', 'c4'}
{'d6', 'a1', 'c4'}
{'b4', 'a1'}
{'d6', 'b4', 'a1'}
{'b4', 'a1', 'c4'}
{'d6', 'b4', 'a1', 'c4'}
{'a3'}
{'d6', 'a3'}
{'c4', 'a3'}
{'d6', 'c4', 'a3'}
{'b4', 'a3'}
{'d6', 'b4', 'a3'}
{'c4', 'b4', 'a3'}
{'d6', 'c4', 'b4', 'a3'}

- no comment

---

没错。这里的关键洞察力在于，对于一个包含N个元素的输入列表，有N+1种可能性：每个元素或没有元素。因此，我们需要额外的列表包装层来考虑要用于给定输入的元素数量，因此进行了转换。 - Karl Knechtel

@KarlKnechtel 加了一个不需要换行的替代方案 :-) - no comment

这是同样的解决方法，只是过滤虚拟值而不是展开列表的虚拟层。不过，我可以理解为什么会有人更喜欢这种美学上的做法。 - Karl Knechtel

@KarlKnechtel 第三个解决方案（也适用于第一个）最漂亮... - no comment