Cartesian product of a dictionary of lists

Question

I'm trying to write some code to test out the Cartesian product of a bunch of input parameters.

I've looked at itertools, but its product function is not exactly what I want. Is there a simple obvious way to take a dictionary with an arbitrary number of keys and an arbitrary number of elements in each value, and then yield a dictionary with the next permutation?

Input:

options = {"number": [1,2,3], "color": ["orange","blue"] }
print list( my_product(options) )

Example output:

[ {"number": 1, "color": "orange"},
  {"number": 1, "color": "blue"},
  {"number": 2, "color": "orange"},
  {"number": 2, "color": "blue"},
  {"number": 3, "color": "orange"},
  {"number": 3, "color": "blue"}
]

I'm pretty sure you don't need any library to do this, but I don't know Python quite well enough to answer. I'd guess that list comprehensions are the trick. — Matt Ball, Mar 08 '11 at 04:00
I'm asking if there exists a ready-made generator that can be easily adapted to do something like this. List comprehensions are not at all relevant. — Seth Johnson, Mar 08 '11 at 04:02

Seth Johnson · Accepted Answer · 2023-04-26T11:38:46.283

95

Ok, thanks @dfan for telling me I was looking in the wrong place. I've got it now:

from itertools import product
def my_product(inp):
    return (dict(zip(inp.keys(), values)) for values in product(*inp.values())

EDIT: after years more Python experience, I think a better solution is to accept kwargs rather than a dictionary of inputs; the call style is more analogous to that of the original itertools.product. Also I think writing a generator function, rather than a function that returns a generator expression, makes the code clearer. So:

import itertools
def product_dict(**kwargs):
    keys = kwargs.keys()
    for instance in itertools.product(*kwargs.values()):
        yield dict(zip(keys, instance))

and if you need to pass in a dict, list(product_dict(**mydict)). The one notable change using kwargs rather than an arbitrary input class is that it prevents the keys/values from being ordered, at least until Python 3.6.

edited Apr 26 '23 at 11:38

answered Mar 08 '11 at 04:18

Seth Johnson

14,762
6
59
85

4

Does the fact that dictionary entries are stored unordered affect this in anyway? – Phani Jun 20 '14 at 20:50
1

This is a very neat code to quickly generate unit test cases (cross-validation set style!) – gaborous Jul 07 '15 at 14:04
2

For Python 3 users. I have an updated version [here](http://stackoverflow.com/a/40623158/621449) – Tarrasch Nov 16 '16 at 02:37
2

@Phani I would say it's okay as the keys and values, even though unordered, are still consistently ordered respectively to each others. – ibizaman Dec 09 '16 at 19:51
@Phani If you are using this list of dictionaries as a list of `**kwargs` to send to a function via `map`, then it's similar to a lot of nested for loops. The difference is that you have no guarantee of which loop is on the outside, and which loop is on the inside. – rudolfbyker Oct 27 '17 at 17:14
Another bonus of doing it on the guaranteed-local `kwargs` is that the user won't be able to modify (intentionally or not) the dictionary keys/values during the iteration. – Seth Johnson Oct 03 '19 at 00:58

score 39 · Answer 2 · edited May 23 '17 at 11:54

39

Python 3 version of Seth's answer.

import itertools

def dict_product(dicts):
    """
    >>> list(dict_product(dict(number=[1,2], character='ab')))
    [{'character': 'a', 'number': 1},
     {'character': 'a', 'number': 2},
     {'character': 'b', 'number': 1},
     {'character': 'b', 'number': 2}]
    """
    return (dict(zip(dicts, x)) for x in itertools.product(*dicts.values()))

edited May 23 '17 at 11:54

Community

1
1

answered Nov 16 '16 at 02:36

Tarrasch

10,199
6
41
57

5

Might add a `.keys()` for clarity on the left side: `(dict(zip(dicts.keys(), x))`. – andrew Feb 27 '20 at 21:06

score 8 · Answer 3 · edited Aug 26 '21 at 09:01

8

By the way, this is not a permutation. A permutation is a rearrangement of a list. This is an enumeration of possible selections from lists.

Edit: after remembering that it was called a Cartesian product, I came up with this:

import itertools
options = {"number": [1,2,3], "color": ["orange","blue"] }
product = [x for x in apply(itertools.product, options.values())]
print([dict(zip(options.keys(), p)) for p in product])

edited Aug 26 '21 at 09:01

Guillaume Jacquenot

11,217
6
43
49

answered Mar 08 '11 at 04:03

dfan

5,714
1
31
27

1

I was trying to explain why looking up "permutations" wasn't helping. I remembered what this actually is: it's a Cartesian product. I would start by looking at itertools.product(). – dfan Mar 08 '11 at 04:09
Yep, done, and thanks for the pointer. But still, welcome to Stack Overflow: an answer should be one that actually provides an answer the question. This belongs as a comment on the question. – Seth Johnson Mar 08 '11 at 04:13
1

@user470379 not really, the original version didn't state Cartesian product – Daniel DiPaolo Mar 08 '11 at 04:14
1

I don't seem to have the ability to comment on anything but my own answers yet. I would have put it there if I could. I'm glad my answer led you to the solution. – dfan Mar 08 '11 at 13:13
Ah, understood. Well, thanks again for your help in setting me on the right track. – Seth Johnson Mar 08 '11 at 15:48
In Python 3, you have to replace `apply(itertools.product, options.values())` with `itertools.product(*options.values())` – GitHunter0 Apr 02 '21 at 22:00

score 4 · Answer 4 · answered Mar 08 '11 at 04:19

4

# I would like to do
keys,values = options.keys(), options.values()
# but I am not sure that the keys and values would always
# be returned in the same relative order. Comments?
keys = []
values = []
for k,v in options.iteritems():
    keys.append(k)
    values.append(v)

import itertools
opts = [dict(zip(keys,items)) for items in itertools.product(*values)]

results in

opts = [
    {'color': 'orange', 'number': 1},
    {'color': 'orange', 'number': 2},
    {'color': 'orange', 'number': 3},
    {'color': 'blue', 'number': 1},
    {'color': 'blue', 'number': 2},
    {'color': 'blue', 'number': 3}
]

answered Mar 08 '11 at 04:19

Hugh Bothwell

55,315
8
84
99

3

I think Python guarantees that keys() and values() and their corresponding iter* will return in the same order. See http://docs.python.org/library/stdtypes.html#dict.items – Seth Johnson Mar 08 '11 at 04:21
@Seth: Excellent! Thank you, that had been bothering me for a while. – Hugh Bothwell Mar 08 '11 at 15:43
you're quite welcome. It's very handy, and especially for this case. If you review my answer, you can see that the iterkeys/itervalues methods will save you from creating a bunch of temporaries, too. – Seth Johnson Mar 08 '11 at 15:50

Cartesian product of a dictionary of lists

4 Answers4

Linked

Related