python - 选择具有最大不同元素数量的三个列表的最有效方法是什么？

Question

例如，给定一个列表列表[[0,1], [1,3], [2,4,5], [3,7,9]]，是否有一种有效的（比强制所有可能性更好）的方法来选择三个列表，从而使所有三个列表中唯一元素的数量最大化？我只能找到启发式方法，最终导致与蛮力相同的最坏情况。这是我的蛮力代码：

def maximum_number_of_elements_brute(list):
    maximum = 0
    maximum_combination = []
    for a in range(len(list)):
        for b in range(a,len(list)):
            for c in range(b,len(list)):
                number_of_elements = len(set(list[a] + list[b] + list[c]))
                if number_of_elements > maximum:
                    maximum = number_of_elements
                    maximum_combination = [a,b,c]
    return (maximum, maximum_combination)

应用于示例列表的函数的结果返回： ([0,2,3], 8)

标签： pythonlistselection

Answer 1

这是最大覆盖问题。它是 NP-hard 的事实表明你不能比蛮力做得更好（尽管固定的k为 3，渐近结果不成立）。当然，你可以做一些可能更快的分支定界：首先考虑最大的集合，如果你有一个至少与剩余集合可以形成的任何集合一样大的联合，则停止搜索。