Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
465 views
in Technique[技术] by (71.8m points)

python - Creating cartesian product for n different types

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?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...