时间戳

首页 > 解决方案 > 从列表列表中选择三个列表的最有效方法，使得所有列表中唯一元素的数量组合大于阈值

python - 从列表列表中选择三个列表的最有效方法，使得所有列表中唯一元素的数量组合大于阈值

问题描述

找出是否可以从列表列表中选择三个列表以使所有列表中唯一元素的数量组合大于某个特定数字的最有效方法是什么？我能想出的最佳解决方案是蛮力：

def maximum_number_of_unique_elements(mylist, threshold):
    for a in range(len(mylist)):
        for b in range(a,len(mylist)):
            for c in range(b,len(mylist)):
                if len(set(mylist[a] + mylist[b] + mylist[c])) >= threshold:
                    return True
   return False

例子：

l = [[0,1,2],[0,1],[0,3,6],[3,7],[4,7]]
t = 7

maximum_number_of_unique_elements(l,t)返回True，因为通过选择列表创建0,2,4了一个带有数字的集合0,1,2,3,4,6,7。

标签： pythonlistselection

解决方案

一个更简单的解决方案是使用itertools.combinations_with_replacement，它允许在不更改代码的情况下设置要使用的列表数量（不是for每个列表的循环）

from itertools import combinations_with_replacement, chain

def maximum_number_of_unique_elements(values, threshold, nb_list=3):
    for parts in combinations_with_replacement(values, r=nb_list):
        if len(set(chain.from_iterable(parts))) >= threshold:
            return True
    return False

combinations_with_replacement每个元素都可以重复，用来combinations获取唯一元素

print(list(combinations('ABC', r=2)))
# [('A', 'B'), ('A', 'C'), ('B', 'C')]

print(list(combinations_with_replacement('ABC', r=2)))
# [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

推荐阅读