Python: combinations of map tuples

Question

I have a list of maps 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?

How exactly does that list of maps look? Did you mean `[{2: ["a", "b"]}, {3: ["b", "c", "d"]}, {4: ["a"]}]`, or is it just `{2: ["a", "b"], 3: ["b", "c", "d"], 4: ["a"]}`, i.e. a map of lists? — tobias_k, Aug 25 '17 at 11:32
To be exactly, it was something like: '{(8, 5): set(['Mt Everest', 'Mt Blanc']), (11, 5): set(['K2'])}'. — 今天春天, Aug 25 '17 at 11:35

score 3 · Accepted Answer · answered Aug 25 '17 at 11:37

Assuming that you "list of dict" is in this form {2: ["a", "b"], 3: ["b", "c", "d"], 4: ["a"]} (as confirmed in comments), you can first use a list comprehension to get all the possible key-value pairs, and then just use itertools.product 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'))]

This is also the most efficient one. I compared it to my iterative/recursive algorithm and it is in most cases a little bit better than the iterative one. — 今天春天, Aug 25 '17 at 11:52
One thing which is not cool about this: I don't want that the superlist contains tuples as elements but rather a list. — 今天春天, Aug 25 '17 at 12:05
@今天春天 If you want a list of lists rather than a list of tuples, just `map` to `list`: `list(map(list, itertools.product(*pairs)))` — tobias_k, Aug 25 '17 at 12:11

englealuze · Answer 2 · 2017-08-25T19:09:02.430

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))

score 0 · Answer 3 · answered Aug 25 '17 at 11:09

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

Python: combinations of map tuples

3 Answers3

Linked