如何用python找到最少数量的列表来覆盖另一个列表的所有元素？

Question

我有一些清单和一个参考清单 我需要找到最少数量的列表，用python覆盖参考列表的所有元素

例如，如果参考列表为：

R = [0,3,10,15]

另一份名单是：

li1 = [0,3]
li2 = [0,10]
li3 = [3,10]
li4 = [3,15]
li5 = [10,15]

覆盖R中每个元素所需的列表的最小数量是li2和li4。我想让它给我一个li2和li4的输出， 列表长度并不总是相同的。 有什么帮助吗

Answer 1

这是蛮力，但我会在将列表放入字典后使用set对象：

from itertools import combinations

R = set([0, 3, 10, 15])
data = dict(
    li1 = [0, 3],
    li2 = [0, 10],
    li3 = [3, 10],
    li4 = [3, 15],
    li5 = [10, 15],
)

for n in range(2, len(data)):
    for keys in combinations(data.keys(), n):
        subset = [data[key] for key in keys]
        if set([item for sublist in subset for item in sublist]) == R:
            break
        
print(keys)

这表明： li1 li5

Answer 2

您可以使用动态规划来解决此问题：

R = set([0,3,10,15])

lists = [
    [0,3], [0,10], [3,10], [3,15], [10,15]
]

def solution(indexes = None, s = None, index = None):
    if indexes is None:
        indexes = []
    if s is None:
        s = set()
    if index is None:
        index = 0
    if s >= R:
        return indexes
    if index >= len(lists):
        return False
    s1 = solution(indexes + [index], s | set(lists[index]), index + 1)
    s2 = solution(indexes, s, index + 1)
    if not s1 and not s2:
        return False
    if not s1:
        return s2
    if not s2:
        return s1
    if len(s1) < len(s2):
        return s1
    return s2

print(solution())

# Output:
# [1, 3]

这是第一种递归方法。您可以使用一种迭代的方法来改进它

Answer 3

OP示例中的预期结果是[li1,li5]和[li2,li4]。优选地，解决方案还应捕获一个列表捕获所有元素的示例，或仅三个列表捕获所有元素的示例

import numpy as np
import pandas as pd
import itertools as it

R = [0,3,10,15]
li1 = [0,3]
li2 = [0,10]
li3 = [3,10]
li4 = [3,15]
li5 = [10,15]

使用列名创建初始空数据帧，并使用值R创建索引

dat = pd.DataFrame(columns=['li1','li2','li3','li4','li5'], index=R)

对于数据帧中的每个列表，我们将指示索引是否存在（即R）。我们使用enumerate将每个列表放入数据帧中

for i,j in list(enumerate([li1,li2,li3,li4,li5])):
    dat.iloc[:,i] = dat.index.isin(j)*1

为了研究哪些列的组合包含所有元素，我们可以使用Itertools查找所有2个成对的组合，并检查所有元素是否都大于零

A = list(it.combinations(['li1', 'li2', 'li3', 'li4', 'li5'], 2))

for i in np.arange(0,len(A)):
    ens = dat[list(A[i])].apply(sum, 1)
    if all(i > 0 for i in ens): print('A combination that contains all elements:', list(A[i]))

结果：

A combination that contains all elements: ['li1', 'li5'] 
A combination that contains all elements: ['li2', 'li4']

为了研究最少数量的列表，可以从一个列表开始，将it.combinations放在1，然后逐步研究两个、三个或更多列表的组合