时间戳

首页 > 解决方案 > Python：查找具有最大总不同值的元组

python - Python：查找具有最大总不同值的元组

问题描述

我有一个整数元组列表。

我想返回一个包含这些元组中的一些（或全部）的新列表，这样整数的总数是最大的，并且没有重复单个整数。

my_tuples = [(1,2), (2,3,4), (1,2,3,4), (3,4,5,6), (4,5), (8,9)]
getGreatestCoverage(my_tuples) 
# expected output is [(1,2), (3,4,5,6), (8,9)]

注意。上面提到的“预期输出”一共包含8个整数，没有重复的整数。我可以通过将要输出的元组数限制为 2 来达到预期的结果：

def getGreatestCoverage_for_2_tuples(my_tuples):
    max_cover = 0
    for idx1, item1 in enumerate(my_tuples):
        for item2 in my_tuples[idx1+1:]:
            coverage = len(set(item1 + item2))
            if coverage >= max_cover:
                max_cover = coverage
                greatest_coverage = (item1, item2)

如果目标是正好返回 2 个元组，这很好用。如果目标是准确返回 3 个元组，则可以添加另一个内部 for 循环。这不满足意图，因为我希望允许任意数量的元组作为可能的输出。

标签： python

解决方案

我不知道这是否是最优雅的解决方案，但它是我现在唯一的一个：

import itertools

#a = [(1,2), (2,3,4), (1,2,3,4), (3,4,5,6), (4,5), (8,9)]
#a = [(1,), (2,), (3,), (4,), (5,), (5,6), (6,7), (8,), (9, 10)]
a = [(0, 1, 2), (0,1), (1,2), (3,4), (4,5)]

def find_largest_group(x):
    max_ = 0
    max_len = max(map(max, x)) -  min(map(min, x)) + 1

    for i in range(1, len(x)+1):
        b = itertools.combinations(x, i)
        for tups in b:
            m = len(set.union(*map(set, tups)))
            if m==len(tuple(itertools.chain.from_iterable(tups))):
                if m==max_len:
                    max_tups = tups
                    break
                else:
                    if m > max_:
                        max_ = m
                        max_tups = tups
    return max_tups

输出：

In [68]: find_largest_group(a)
Out[68]: ((0, 1, 2), (3, 4))

推荐阅读