Python recursion over dictionary of set values permutations

Question

I'm trying to get all combinations of a dictionary recursively but I can't wrap my head around how to get the output properly. Essentially a depth-first search which saves the input in a (key, value) tuple or something similar. Any help appreciated. Thanks /Fred

input:

d = {"item1": {1, 2},
     "item2": {3, 4},
     "item3": {5, 6}}

output:

"item1" 1
"item2" 3
"item3" 5
"item3" 6
"item2" 4
"item3" 5
"item3" 6
"item1" 2
"item2" 3
"item3" 5
"item3" 6
"item2" 4
"item3" 5
"item3" 6

edit: The perms needs to be drawn recursively. Maybe an illustration clarifies a bit:

A tree structure worked but was not generalised enough for my purposes, and cumbersome to edit.

Update: Currently I'm hardcoding these like so:

d = {"item1": {1, 2},
     "item2": {3, 4},
     "item3": {i for i in range(1, 5)}}

for k in d["item1"]:
    print ("item1", k)
    for j in d["item2"]:
        print ("item2", j)
        for i in d["item3"]:
            print("item3", i)

It seems obvious where the recursion happens but I'm still having troubles with it. Thank you all for all suggestions so far! Also it's in python3 if that makes any difference.

_all combinations of a dictionary_ You have to be more precise. The keys? The values? — Elmex80s, May 04 '17 at 02:12
@JoeD posted an elegant answer featuring something like `[[perm for perm in itertools.product([k], v)] for k, v in d.items()]`, now deleted. — Paulo Scardine, May 04 '17 at 02:17
I don't think a dictionary is the proper data structure for what you're trying to achieve as an output. Additionally, your diagram only has `1` and `2` as the item values, is this what you want your output to have? — AetherUnbound, May 04 '17 at 15:53
@AetherUnbound Yes, what I am trying to do is essentially a gridsearch on a different script altogether, the "itemx" is a function call and the integer is the argument that goes with it, hence the structure: I'm trying to run all possible combinations of the script but with each option only appearing once, like the tree structure. Currently I'm hardcoding it but it is very cumbersome to edit. Will look into alternative structures thanks — Fred, May 05 '17 at 20:13
@Fred you might consider simply building a tree: http://stackoverflow.com/questions/2358045/how-can-i-implement-a-tree-in-python-are-there-any-built-in-data-structures-in. Let me know if this helps! I'd be happy to chat further about better ways to structure this data :) — AetherUnbound, May 07 '17 at 02:39
@AetherUnbound a node tree worked but was a bit too cumbersome to generalise so I opted to not create an answer with it since I had to use another data structure than the one I had above. Thanks for the suggestion though :) — Fred, May 09 '17 at 22:08

Joe D · Accepted Answer · 2017-05-04T04:14:36.477

3

This will return a list of permutations.

from itertools import product

perms = [[perm for perm in product([key], d[key]) for key in d]]

An update in case you're looking for a possible combinations of key values pairs which would be 18 in total.

[print(prod) for prod in product(d, itertools.chain.from_iterable(d.values()))]

outputs:

('item3', 5)
('item3', 6)
('item3', 1)
('item3', 2)
('item3', 3)
('item3', 4)
('item1', 5)
('item1', 6)
('item1', 1)
('item1', 2)
('item1', 3)
('item1', 4)
('item2', 5)
('item2', 6)
('item2', 1)
('item2', 2)
('item2', 3)
('item2', 4)

edited May 04 '17 at 04:14

answered May 04 '17 at 01:57

Joe D

378
1
9

There is an extra `in` before `d[key]` and `.keys()` is redundant because `... for key in d.keys()` is the same as `... for key in d` - otherwise nice answer. – Paulo Scardine May 04 '17 at 02:01
Very nice solution, it doesn't solve the recursive part though. There should be 14 outputs in total which is where my knowledge runs short. Maybe permutation is not the right word I used. Added a tree diagram to illustrate the problem further, hence I was thinking depth-first search would do the trick, but couldn't figure out how to output a tuple for every node. – Fred May 04 '17 at 03:28
You could also write it without imports like so: `perms = [(field, item) for field, items in d.items() for item in items]` – Fred May 04 '17 at 03:39
2

@Fred okay so just to clarify, you want all combinations of a key with any of the values in dictionary? The example you gave has duplicates, is that what you're shooting for? – Joe D May 04 '17 at 03:49

Paulo Scardine · Answer 2 · 2017-05-04T03:04:00.027

How about this:

>>> for pair in itertools.chain(*([(k, i) for i in v] for k, v in d.items())):
    print(pair)

('item2', 3)
('item2', 4)
('item3', 5)
('item3', 6)
('item1', 1)
('item1', 2)

Or a bit more legible:

def key_value_permutations(d):
    for k, v in d:
       for p in itertools.product([k], v):
           yield p

Then:

>>> for p in key_value_permutations(d):
    print p

('item2', 3)
('item2', 4)
('item3', 5)
('item3', 6)
('item1', 1)
('item1', 2)

Both solutions use generators because they assume your dicts and sets will be bigger than in the sample you provided and you will just iterate over it so you don't really need to create a huge list in memory. If the size is negligible, list comprehensions may be faster.

You can't count on consistent ordering because both dicts and sets have no guaranteed ordering.

score 1 · Answer 3 · answered May 04 '17 at 01:41

1

Is this what you're looking for?

for first_level in d:
     item_list = d[first_level]
     for item in item_list:
             print((first_level, item))

Output

('item2', 3)
('item2', 4)
('item3', 5)
('item3', 6)
('item1', 1)
('item1', 2)

answered May 04 '17 at 01:41

AetherUnbound

1,714
11
10

Python recursion over dictionary of set values permutations

3 Answers3