如何在Python中找到两个列表中浮点数元组范围的交集？

Question

我有两个形式为：

的列表：

lst1 = [(1.2, 4), (5, 8), (19, 21), (24.5, 26)]
lst2 = [(1, 3), (6.55, 14.871), (22, 23)]

我希望获取的输出是：

output = [(1.2, 3), (6.55, 8)]

基本上，我希望得到这两个列表中元组定义的范围的交集。

您可以假设：

1. the indices to be ordered within a given list. For example, in lst2:

   1 < 6.55 < 22
   

2. the ranges to be valid (within a tuple, the startVal<=endEndVal). In lst2:

   1 < 3  and 6.55 < 14.871 and 22 < 23
   

有什么高效的方法可以实现这个目标吗？

- Melsauce

Answer 1

我认为在两个列表长度相同的情况下，使用列表推导式是最好的方法。

为了易读性，将两个列表分开：

Original Answer：最初的回答

# get the min max ranges
a = [(max(i[0], j[0]),min(i[1],j[1])) for i,j in zip(lst1, lst2)]
# check that min is smaller than max
a = [(i,j) for (i,j) in a if i < j]

最初的回答

或者在一个列表中：

a = [(i,j) for (i,j) in [(max(i[0], j[0]),min(i[1],j[1])) for i,j in zip(lst1, lst2)] if i < j]

- Linda

---

对于输入 lst1 = [(1.2, 4), (5, 8), (19, 21), (24.5, 26)] 和 lst2 = [(1, 3), (6.55, 14.871), (22, 25)]，期望的输出是 [(1.2, 3), (6.55, 8), (24.5, 25)]。但你的程序输出为 [(1.2, 3), (6.55, 8)]。 - bumblebee

不，问题中明确指定了：“我想要的输出是：output = [(1.2, 3), (6.55, 8)]”。最后一个范围是无效的，因此不应出现在输出中。 - Linda

是的，但 lst1[3] 和 lst2[2] 相交，它们的交集是 (24.5, 25)。 - bumblebee

@Linda，你代码的问题在于它只比较元组的第i个元素（因为你使用了zip）。所以如果lst1的第一个元素是(0,0)，它将与(1,3)进行比较，并跳过(1.2,4)与(1,3)之间的比较以及所有其他点 - 这将给出一个空列表作为解决方案，这是不正确的。 - Ricky Kim

@RickyKim 我明白了，我想我误解了问题。我以为目的是一对一的比较。 - Linda

Answer 2

使用 itertools 和 heapq.merge：

lst1 = [(1.2, 4), (5, 8), (19, 21), (24.5, 26)]
lst2 = [(1, 3), (6.55, 14.871), (22, 25)]

from heapq import merge
from itertools import tee, groupby

m1, m2 = tee(merge(lst1, lst2, key=lambda k: k[0]))
next(m2, None)

out = []
for v, g in groupby(zip(m1, m2), lambda k: k[0][1] < k[1][0]):
    if not v:
        l = [*g][0]
        out.append((max(i[0] for i in l), min(i[1] for i in l)))

print(out)

输出：

[(1.2, 3), (6.55, 8), (24.5, 25)]

- Andrej Kesely

---

这不是通过比较两个列表来查找交集，而是通过合并来进行的，我不确定这是否是OP想要的。例如，输入lst1 = [(1.2, 4),(1, 3), (5, 8), (19, 21), (24.5, 26)]和lst2 = [(6.55, 14.871), (22, 25)]仍然输出相同的结果，但您可能希望输出[(6.55, 8), (24.5, 25)]。 - Ricky Kim

抱歉，我意思是 lst1 = [(1, 3), (1.2, 4), (5, 8), (19, 21), (24.5, 26)]。 - Ricky Kim

@RickyKim 是的，在这种情况下，我的脚本返回 [(1.2, 3), (6.55, 8), (24.5, 25)]，但这取决于操作的输入。也许 ops 列表没有重叠的区间。 - Andrej Kesely

Answer 3

使用迭代器的解决方案。我使用一个 while 循环，该循环保持活动状态，直到运行在列表上的两个迭代器都用尽为止。

lst1 = [(1.2, 4), (5, 8), (19, 21), (24.5, 26)]
lst2 = [(1, 3), (6.55, 14.871), (22, 23)]

itr1 = iter(lst1)
itr2 = iter(lst2)
on1 = True
on2 = True

rng1 = next(itr1)
rng2 = next(itr2)
res = []

while on1 or on2:
    ll = max(rng1[0], rng2[0])
    rr = min(rng1[1], rng2[1])
    if ll < rr:
        res.append((ll, rr))

    if on1 and on2:
        if rng1[0] < rng2[0]:
            try:
                rng1 = next(itr1)
            except StopIteration:
                on1 = False
        else:
            try:
                rng2 = next(itr2)
            except StopIteration:
                on2 = False
    elif on1:
        try:
            rng1 = next(itr1)
        except StopIteration:
            on1 = False
    elif on2:
        try:
            rng2 = next(itr2)
        except StopIteration:
            on2 = False

if len(res) > 1 and res[-1] == res[-2]:
    res.pop(-1)
print(res)

使用您提供的样例输入，输出结果为：[(1.2，3)，(6.55，8)]

- Valentino

Answer 4

创建一个简单的函数，以获取两个范围的交集范围。

    def get_intersect(r1, r2):
            left = max(r1[0], r2[0])
            right = min(r1[1], r2[1])
            if left>right:
                return None
            return (left,right)

2. 通过双重循环获取所有交集

    for i1 in lst1:
        for i2 in lst2:
            ia = get_intersect(i1, i2)
            if ia!=None:
                print(ia)

如果您在循环中添加一些条件，它会更快。

- Junhee Shin

---

如果你在循环中添加一些条件，它会更快。那么你应该添加它们吗？ - Ricky Kim