45649

Python: combinations of map tuples

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

Recommend

  • How to add programatically add new div using Enyojs and attach to the subscriber of opentok
  • spoj factorial (time limit exceeded error). How can i improve my solution? [closed]
  • Correctly executing bicubic resampling
  • How to programmatically select a UITextField for editing
  • How to read utf-16 file into utf-8 std::string line by line
  • C#, Microsoft interop, Excel numberformat problem
  • How do I set file permissions when opening a file in C++?
  • Store a two value combination
  • How to read image field from MSSQL with PHP
  • Blackjack minimax algorithm
  • get Unique info for a machine in asp.net
  • Convert a binary to decimal using MySQL
  • Data.table: Add rows for missing combinations of 2 factors without losing associated descriptive fac
  • Sort Data.Map by value and get all biggest values
  • @media syntax / possible combinations
  • Fetch a tree with Neo4j
  • Intellij Idea Terminal shortcut not working
  • Merge arrays by common column values in julia
  • Extracting individual digits from a float
  • In matplotlib, how do you change the fontsize of a single figure?
  • Creating a DropDownList
  • Spring: No transaction manager has been configured
  • accepts_nested_attributes_for practical form use for in Rails 3
  • Authentication in Play! and RestEasy
  • Object and struct member access and address offset calculation
  • presentShareDialogWithParams posts to FB wall, but callback handler results say error
  • How to match http request and response using Jersey ContainerRequestFilter and ContainerResponseFilt
  • Time complexity of a program which involves multiple variables
  • Checking free space on FTP server
  • script to move all files from one location to another location
  • How to make Safari send if-modified-since header?
  • How do you troubleshoot character encoding problems?
  • How to pass list parameters for each object using Spring MVC?
  • Setting background image for body element in xhtml (for different monitors and resolutions)
  • JaxB to read class hierarchy
  • Running Map reduces the dimensions of the matrices
  • How to Embed XSL into XML
  • UserPrincipal.Current returns apppool on IIS
  • Android Heatmap on canvas or ImageView
  • Conditional In-Line CSS for IE and Others?