选择具有最大不同元素数量的三个列表的最有效方法是什么? [英] What is the most efficient way to select three lists with maximum number of different elements?

问题描述

给定一个列表列表，例如 [[0,1]，[1,3]，[2,4,5]，[3,7,9]] ，有没有一种有效的方法(强行强行使用所有可能性)选择三个列表，以使所有三个列表中的唯一元素的数量最大化?我只能找到启发式的方法，最终会导致与蛮力同样的最坏情况.这是我的蛮力代码:

Given a list of lists, e.g. [[0,1], [1,3], [2,4,5], [3,7,9]], is there an efficient (better than brute forcing all possibilities) way to select three lists such that the number of unique elements in all three lists combined is maximized? I can only find heuristic ways, that ultimately result in the same worst-case as brute force. This is my brute force code:

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)

The result of the function applied to the example list returns: ([0,2,3], 8)

推荐答案

这是最大覆盖率问题.它是NP硬的事实表明您不能做得比蛮力好得多(尽管将 k 固定为3，但渐近结果并不成立).当然，您可以做一些可能更快的分支定界方法:首先考虑最大的集合，如果搜索的并集至少与其余集合相同，则停止搜索可以形成.

This is the maximum coverage problem. The fact that it is NP-hard suggests that you can’t do much better than brute force (although with a fixed k of 3 the asymptotic result doesn’t hold). Certainly you can do some branch-and-bound that is likely to be faster: consider the largest sets first, and stop part if the search if you have a union at least as large as any that remaining sets could form.

这篇关于选择具有最大不同元素数量的三个列表的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！