python - 获取列表列表的powerset

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循环，但由于我不能保证我的循环有多少（这也会使我的时间复杂度为 O(N^x)），所以我使用key了并且根据这篇文章：sitertools.chainitertools.combinations

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

问题是这只考虑了单个列表中的元素，因此忽略了约束：“最多从每个列表中获取一个以上的元素”。扁平化列表会忽略类别，所以我没有尝试这样做。

任何解决此问题的见解将不胜感激。

标签： pythonhashcombinations

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'}