时间戳

首页 > 解决方案 > 查找共同构成目标列表的最小列表的算法

python - 查找共同构成目标列表的最小列表的算法

问题描述

假设我有以下内容：

{
  'a': [1, 2, 3],
  'b': [1, 5],
  'c': [3, 4, 5],
  'd': [1, 3, 5],
  'e': [4]
}

想要的结果是['a', 'c'] 因为我想找到哪些数组合并在一起（并删除重复项）表格[1 , 2, 3, 4, 5]

除了将哪些数组合并在一起形成所需的结果之外，我还想找到要合并的最小数组以获得所需的结果（因为例如也['a', 'd', 'e']给出了所需的结果，但这['a', 'c']是一个更好的解决方案）

PS。上面的字典只是一个例子，原来的字典有很多键，每个键都有数百个值。

标签： pythonlistmerge

解决方案

沿着这条线的东西应该起作用。您需要根据您是否希望对其进行排序等进行一些调整。此解决方案假定顺序无关紧要。

从最小到最大打印解决方案：

import itertools

input = {
  'a': [1, 2, 3],
  'b': [1, 5],
  'c': [3, 4, 5],
  'd': [1, 3, 5],
  'e': [4]
}

solution = [1,2,3,4,5]
for i in range(1,len(input.keys())):
    for combination in itertools.combinations(input, i):
        pot = list(set(itertools.chain.from_iterable(input[k] for k in combination)))
        if pot == solution:
            print("This is a solution:", combination)

推荐阅读