Question:

I have a <strong>list of maps</strong> in Python looking like this:

```
2: a, b
3: b, c, d
4: a
```

And I want to create all conbinations of key-value-pairs, i.e.:

```
(2,a)(3,b)(4,a)
(2,a)(3,c)(4,a)
(2,a)(3,d)(4,a)
(2,b)(3,b)(4,a)
(2,b)(3,c)(4,a)
(2,b)(3,d)(4,a)
```

I neither know the size of the maps nor the size of the list, but the list will never have more than 4 elements. I can assume that the keys are unique but not that they are always 1,2,3,4 or 0,1,2,3 as depicted in the example above.

What is the smartest/most efficient way to solve this?

Answer1:Assuming that you "list of dict" is in this form `{2: ["a", "b"], 3: ["b", "c", "d"], 4: ["a"]}`

(as confirmed <a href="https://stackoverflow.com/questions/45878288/python-combinations-of-map-tuples/45880526#comment78719265_45878288" rel="nofollow">in comments</a>), you can first use a list comprehension to get all the possible key-value pairs, and then just use <a href="https://docs.python.org/3/library/itertools.html#itertools.product" rel="nofollow">`itertools.product`

</a> to get the combinations of those pairs.

```
>>> d = {2: ["a", "b"], 3: ["b", "c", "d"], 4: ["a"]}
>>> pairs = [[(k, v) for v in d[k]] for k in d]
>>> list(itertools.product(*pairs))
[((2, 'a'), (3, 'b'), (4, 'a')),
((2, 'a'), (3, 'c'), (4, 'a')),
((2, 'a'), (3, 'd'), (4, 'a')),
((2, 'b'), (3, 'b'), (4, 'a')),
((2, 'b'), (3, 'c'), (4, 'a')),
((2, 'b'), (3, 'd'), (4, 'a'))]
```

Using your "actual" example:

```
>>> d = {(8, 5): set(['Mt Everest', 'Mt Blanc']), (11, 5): set(['K2'])}
>>> pairs = [[(k, v) for v in d[k]] for k in d]
>>> list(itertools.product(*pairs))
[(((8, 5), 'Mt Everest'), ((11, 5), 'K2')),
(((8, 5), 'Mt Blanc'), ((11, 5), 'K2'))]
```

Answer2:Look at the base case first. If there is only one map `2, a, b`

, solutions are

```
initial_sol = (2,a)
(2,b)
```

If I now add one more map `3, b, c, d`

a new solution can be generated by appending each tuple in the new map to the previous solutions

```
second_sol = (2,a)(3,b)
(2,a)(3,c)
(2,a)(3,d)
(2,b)(3,b)
(2,b)(3,c)
(2,b)(3,d)
```

Now assume that I have already a procedure solving this problem for a set of given maps, by extending the solution with a newly added map, the problem of larger maps can be solved

```
import itertools
# supose the maps you want to solve are in this format
themaps=[[2,'a','b'],[3,'b','c','d'],[4,'a']]
# a little work is required to reformat its structure
themaps=list(map(lambda x: list(map(lambda y: (x[0], y), x[1:])),themaps))
def flatmap(func, *iterable):
return itertools.chain.from_iterable(map(func, *iterable))
# method of appending each element from the newly added map to current solutions
# in order to extend the old solutions to new solutions of larger maps
def next_solution(sol, anewmap):
return list(flatmap(lambda x: map(lambda y: x+[y], anewmap), sol))
# a reduced set of maps
def smaller(M): return M[0:-1]
# newly added map
def newmap(M): return M[-1]
# solutions at base case
def base_solution(M): return [[i] for i in M[0]]
# function to solve the problem with any given set of maps
# Notice how this reduces the problem of solving larger maps to smaller maps
def solve_it(allmaps):
if allmaps == []:
return []
elif len(allmaps) == 1:
return base_solution(allmaps)
else:
return next_solution(solve_it(smaller(allmaps)), newmap(allmaps))
print(solve_it(themaps))
```

Answer3:Finally figured out an algorithm - here is the pseudo code:

```
function comb_map(list)
if list is empty
return empty list
else
current_element = list.pop()
result_list = empty list
for each element in current_list.values #call it: b
for each element in comb_map(list) #call it: as
add b to as
add as to result_list
return result_list
```