为 n 个不同类型创建笛卡尔积 [英] Creating cartesian product for n different types

问题描述

考虑我有一个包含 n 个由键表示的不同类型的字典:x1, x2 ..xn

Consider I have a dict holding n different types represented by keys:x1, x2 ..xn

为了简单起见，我们举一个小例子:

For simplicity let's take a small example:

{"x1":["foo1", "goo1" ,"doo1"], "x2":["foo2","goo2"]}

我想计算上面的笛卡尔积.我的输出应该是:

I want to calculate cartesian product of the above. My output should be:

{"output":[{"x1":"foo1", "x2":"foo2"}, {"x1":"foo1", "x2":"goo2"}, {"x1":"goo1", "x2":"foo2"} , {"x1":"goo1", "x2":"goo2"}, {"x1":"doo1", "x2":"foo2"} {"x1":"doo1", "x2":"goo2"}]}

我是否应该遍历输入字典键中的每个 unique pair 并计算它们的笛卡尔积并附加它们的值?如果出现另一个值，例如 x3，我该如何连接其余的值?

Should I traverse each unique pair out of input dictionary keys and calculate their cartesian product and append their values? How do I concatenate the rest of values if another value appears let's say x3?

在这种方法中，我将计算 x1*x2 值的笛卡尔积然后是 x2*x3 值以及如何将结果合并为 x1*x2*x3?

In this kind of approach I will calculate cartesian product for x1*x2 values and then x2*x3 values and how do I merge the results to be x1*x2*x3?

你能想到一个更简单、更高效的算法吗?或者应该是这样?

Can you think of a more simple algorithm and an efficient one? Or this should be the way?

推荐答案

您可以使用 itertools.product 得到笛卡尔积.要为新的 dict 重建 key-value 对，您可以先冻结键的顺序(.keys 和 .values 排序不是保证在所有 Python 版本中，除非 dict 没有改变)通过在获取笛卡尔积之前调用它的 list .笛卡尔积的值现在保持键的顺序，结果字典的键值对现在可以安全用 zip 构造:

You can use itertools.product to get the cartesian product. To reconstruct the key-value pairs for the new dicts, you can first freeze the order of keys (.keys and .values ordering is not guaranteed across all Python versions unless dict is not altered) by calling list on it before taking the cartesian product. The values from the cartesian product now maintain the order of the keys and the key-value pairs for the resulting dicts can now be safely constructed with zip:

from itertools import product
from pprint import pprint

dct = {"x1":["foo1", "goo1" ,"doo1"], "x2":["foo2","goo2"]}

keys = list(dct)
lst = [dict(zip(keys, vals)) for vals in product(*[dct[k] for k in keys])]
pprint(lst)

<小时>

[{'x1': 'foo1', 'x2': 'foo2'},
 {'x1': 'foo1', 'x2': 'goo2'},
 {'x1': 'goo1', 'x2': 'foo2'},
 {'x1': 'goo1', 'x2': 'goo2'},
 {'x1': 'doo1', 'x2': 'foo2'},
 {'x1': 'doo1', 'x2': 'goo2'}]

这将扩展到与原始列表包含的值列表一样多的值.

This will scale to as many value lists as the original list contains.

这篇关于为 n 个不同类型创建笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！