Python：基于基数属性的过滤器集/元组列表

Question

我正在寻找一种根据元组出现的次数来过滤一组（或列表）元组的方法。 项目出现在元组的另一个位置之一。

我当前的目标有点复杂，所以我将问题分为三个较小的步骤。

1。让我们从最简单的情况开始，只有一个值，仅适用于元组的第一个元素

例如：

my_filter([(1,2),(1,3),(2,4),(3,1),(3,4),(3,5),(5,2),(5,4)], 2)

应该返回：

[(1,2),(1,3),(5,2),(5,4)]

因为这些是唯一链接元组第一项的元组，在整个列表中仅出现两次。

简单的做法是：对于列表中元组的每个第一个元素，计算该元素作为所有元组中的第一个元素出现的次数，如果计数与所选数字匹配，则首先添加具有该元素的所有元组位置。

但我觉得这太不理想了，我必须迭代列表中的每个可能的值，我肯定错过了更好的方法。

2。做到互惠互利

理想情况下，它希望能够基于元组的第二个元素应用相同的处理，并使用另一个基数参数

例如：

my_filter([(1,2),(1,3),(2,4),(3,1),(3,4),(3,5),(5,2),(5,4)], 2, 1)

这里我们只想保留第一个元素恰好出现两次但第二个元素仅出现一次的元组（两个条件的交集）。这应该返回：

[(1,3)]

3.推广到多个值

my_filter([(1,2),(1,3),(2,4),(3,1),(3,4),(3,5),(5,2),(5,4)], 2, [1,3])

在这种情况下，我们允许基数过滤器采用多个可能的值。在此示例中，我们希望保留第一个元素恰好出现两次（在第一个位置）而第二个元素出现一次或三次（在第二个位置）的元组。这应该返回：

[(1,3),(5,4)]

再一次，我可以毫无问题地编写一个简单的解决方案，只需迭代每个允许的值并连接结果集，但我正在寻找更智能的东西。

我觉得 itertools 库中可能有一些有用的功能，但我对它不够满意。有什么建议吗？谢谢。

Answer 1

这是第 2 部分和第 3 部分的线性时间 (

O(n)

) 解决方案（第 1 部分可以通过一些调整来实现）：

首先我们将第二个和第三个参数转换为一个集合 (O(n))。

然后我们计算位置 0 和 1 处每个元素的频率，同样是 O(n)。

然后我们迭代列表并检查它是否符合我们的标准。集合查找的时间复杂度为 O(1)，所以这个东西再次高效，总体为 O(n)。

from collections import Counter


def my_filter(list, first, second):
    first_set = set(first)
    second_set = set(second)
    first_counter = Counter(a for (a, _) in list)
    second_counter = Counter(b for (_, b) in list)
    return [
        (a, b)
        for (a, b) in list
        if first_counter[a] in first_set and second_counter[b] in second_set
    ]


print(
    my_filter(
        [(1, 2), (1, 3), (2, 4), (3, 1), (3, 4), (3, 5), (5, 2), (5, 4)], [2], [1]
    )
)

print(
    my_filter(
        [(1, 2), (1, 3), (2, 4), (3, 1), (3, 4), (3, 5), (5, 2), (5, 4)], [2], [1, 3]
    )
)

输出：

[(1, 3)]
[(1, 3), (5, 4)]