如何用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

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，然后逐步研究两个、三个或更多列表的组合