python - Creating cartesian product for n different types

Question

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"}]}

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?

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?

Answer 1

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.