Python:映射元组的组合

Question

我在Python中有一个地图列表，如下所示：

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

我想创建键值对的所有组合，即：

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

我既不知道地图的大小，也不知道列表的大小，但列表永远不会超过 4 个元素。我可以假设键是唯一的，但不是它们总是 1,2,3,4 或 0,1,2,3，如上例所示。

解决此问题的最聪明/最有效的方法是什么？

Answer 1

假设你的"字典列表"是这种形式{2: ["a", "b"], 3: ["b", "c", "d"], 4: ["a"]}(如注释中所确认的(，你可以首先使用列表推导来获取所有可能的键值对，然后只使用itertools.product来获取这些对的组合。

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

使用您的"实际"示例：

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

Answer 2

先看基本情况。如果只有一个地图2, a, b，则解为

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

如果我现在再添加一个地图3, b, c, d通过将新映射中的每个元组附加到以前的解决方案中，可以生成新的解决方案

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)

现在假设我已经有一个程序来解决一组给定地图的这个问题，通过使用新添加的地图扩展解决方案，可以解决较大地图的问题

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

Answer 3

终于想出了一个算法——这是伪代码：

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