来自不同尺寸集合的元素的所有可能组合

Question

我正在创建一个供我私人使用的工具，但我遇到了一个复杂的组合问题。我有 7 个类似格式的子字典：{"D1": {"A": 1, "B": 3, "C":6}, "D2": {"D": 4}, "D3": {"E": 8, "F": 12, "G": 2}. "D4": {"H": 9, "I": 3}. "D5": {"J": 2}, "D6": {"K": 8, "L": 1}, "D7": {"M": 2}}我需要的是生成所有可能的字典，这些字典将以这种格式组合每个字典中的 1 个元素：[{"D1": "A", "D2": "D", "D3": "E", "D4": "H", "D5": "J", "D6": "K", "D7": "M"}, {"D1": "A", "D2": "D", "D3": "F", "D4": "I", "D5": "J", "D6": "L", "D7": "M"}, and all other possible combinations]输出应该是所有 DX 字典中元素的所有可能唯一组合的列表。我可能能够使用一些非常复杂、难看、嵌套的带有大量 if 的循环来解决这个问题，但可能有一种非常好的方法可以在 itertools 或类似的东西中实现它。对有效完成这项任务有任何帮助吗？这个任务需要在大量这样的字典上重复，所以性能是关键。谢谢！

Answer 1

看起来有点复杂，但一个相当简单的解决方案：

import itertools

D = [D1, D2, D3, D4, ...]

dicts = [

    dict(zip([f'D{i+1}' for i in range(len(D))], iter)) 

    for iter in itertools.product(*[list(d.keys()) for d in D])

]

dict_1 = dicts[0]

dict_2 = dicts[1]

...

dicts = [

    {'D1': 'A', 'D2': 'D', 'D3': 'E', 'D4': 'H'},

    {'D1': 'A', 'D2': 'D', 'D3': 'E', 'D4': 'I'},

    {'D1': 'A', 'D2': 'D', 'D3': 'F', 'D4': 'H'},

    {'D1': 'A', 'D2': 'D', 'D3': 'F', 'D4': 'I'},

    ...

]

这个怎么运作：

生成所有键组合

itertools.product(*[list(d.keys()) for d in D])

将组合与适当的字典名称结合起来

zip([f'D{i+1}' for i in range(len(D))], iter))

将这两个部分组合起来并将它们中的每一个转换为字典

[

    dict(zip([f'D{i+1}' for i in range(len(D))], iter)) 

    for iter in itertools.product(*[list(d.keys()) for d in D])

]

Answer 2

你想要的是你的字典的笛卡尔积。幸运的是，itertools定义了一个product完全可以做到这一点的函数。

当用作可迭代对象时，adict将产生其键，因此product(D1, D2, ...)将直接产生键元组，例如('A', 'D', 'F', ...).

您需要进行一些调整才能获得所需的输出：

from pprint import pprint

import itertools

dicts = [

    {"A": 1, "B": 3, "C":6},

    {"D": 4},

    {"E": 8, "F": 12, "G": 2},

    {"H": 9, "I": 3}

]

r = [

    {f"D{i}": key for i, key in enumerate(x, 1)}

    for x in itertools.product(*dicts)

]

pprint(r)

输出：

[{'D1': 'A', 'D2': 'D', 'D3': 'E', 'D4': 'H'},

 {'D1': 'A', 'D2': 'D', 'D3': 'E', 'D4': 'I'},

 {'D1': 'A', 'D2': 'D', 'D3': 'F', 'D4': 'H'},

 {'D1': 'A', 'D2': 'D', 'D3': 'F', 'D4': 'I'},

 {'D1': 'A', 'D2': 'D', 'D3': 'G', 'D4': 'H'},

 {'D1': 'A', 'D2': 'D', 'D3': 'G', 'D4': 'I'},

 {'D1': 'B', 'D2': 'D', 'D3': 'E', 'D4': 'H'},

 {'D1': 'B', 'D2': 'D', 'D3': 'E', 'D4': 'I'},

 {'D1': 'B', 'D2': 'D', 'D3': 'F', 'D4': 'H'},

 {'D1': 'B', 'D2': 'D', 'D3': 'F', 'D4': 'I'},

 {'D1': 'B', 'D2': 'D', 'D3': 'G', 'D4': 'H'},

 {'D1': 'B', 'D2': 'D', 'D3': 'G', 'D4': 'I'},

 {'D1': 'C', 'D2': 'D', 'D3': 'E', 'D4': 'H'},

 {'D1': 'C', 'D2': 'D', 'D3': 'E', 'D4': 'I'},

 {'D1': 'C', 'D2': 'D', 'D3': 'F', 'D4': 'H'},

 {'D1': 'C', 'D2': 'D', 'D3': 'F', 'D4': 'I'},

 {'D1': 'C', 'D2': 'D', 'D3': 'G', 'D4': 'H'},

 {'D1': 'C', 'D2': 'D', 'D3': 'G', 'D4': 'I'}]

Answer 3

itertools product是你的朋友：

from itertools import product

d = {"D1": {"A": 1, "B": 3, "C":6}, 

     "D2": {"D": 4},  

     "D3": {"E": 8, "F": 12, "G": 2}, 

     "D4": {"H": 9, "I": 3}, 

     "D5": {"J": 2}, 

     "D6": {"K": 8, "L": 1}, 

     "D7": {"M": 2}}

res = []

for c in product(*(v.keys() for _, v in d.items())):

  res.append(dict(zip(d.keys(), c)))

列表理解版本将是：

res = [dict(zip(d.keys(), c)) for c in product(*(v.keys() for _, v in d.items()))]

产生：

[{'D1': 'A', 'D2': 'D', 'D3': 'E', 'D4': 'H', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'E', 'D4': 'H', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'E', 'D4': 'I', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'E', 'D4': 'I', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'F', 'D4': 'H', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'F', 'D4': 'H', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'F', 'D4': 'I', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'F', 'D4': 'I', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'G', 'D4': 'H', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'G', 'D4': 'H', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'G', 'D4': 'I', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'A', 'D2': 'D', 'D3': 'G', 'D4': 'I', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'E', 'D4': 'H', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'E', 'D4': 'H', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'E', 'D4': 'I', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'E', 'D4': 'I', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'F', 'D4': 'H', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'F', 'D4': 'H', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'F', 'D4': 'I', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'F', 'D4': 'I', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'G', 'D4': 'H', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'G', 'D4': 'H', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'G', 'D4': 'I', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'B', 'D2': 'D', 'D3': 'G', 'D4': 'I', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'E', 'D4': 'H', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'E', 'D4': 'H', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'E', 'D4': 'I', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'E', 'D4': 'I', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'F', 'D4': 'H', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'F', 'D4': 'H', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'F', 'D4': 'I', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'F', 'D4': 'I', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'G', 'D4': 'H', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'G', 'D4': 'H', 'D5': 'J', 'D6': 'L', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'G', 'D4': 'I', 'D5': 'J', 'D6': 'K', 'D7': 'M'},

 {'D1': 'C', 'D2': 'D', 'D3': 'G', 'D4': 'I', 'D5': 'J', 'D6': 'L', 'D7': 'M'}]

优点和缺点

（+）与其他答案不同，这个答案不依赖于模式之后的 subdicts 的命名D<i>；他们可以被称为任何东西。

(-) 必须保留 dict 的顺序，因此您需要 Python 3.5+