Python: Combinations Of Map Tuples

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,

Solution 1:

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

Solution 2:

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

Solution 3:

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