How to find intersections of ranges of float tuples across two lists in python?

Question

I have two lists of the form:

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

The output I am looking to get is:

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

Basically, I want the intersections between the ranges defined by the tuples across the two lists.

You can assume-

the indices to be ordered within a given list. For example, in lst2:
```
1 < 6.55 < 22
```
the ranges to be valid (within a tuple, the startVal<=endEndVal). In lst2:
```
1 < 3  and 6.55 < 14.871 and 22 < 23
```

What is an efficient way to achieve this?

Linda · Accepted Answer · 2019-07-31 14:06:54Z

2

I think the best way to do this is with a list comprehension, given that both lists are the same length.

in two lists for readability:

# 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]

or in one list:

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]

answered Jul 31, 2019 at 14:06

Linda

1,1391 gold badge11 silver badges27 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

bumblebee Over a year ago

For the input lst1 = [(1.2, 4), (5, 8), (19, 21), (24.5, 26)] and lst2 = [(1, 3), (6.55, 14.871), (22, 25)], the expected output is [(1.2, 3), (6.55, 8), (24.5, 25)]. But the output of your program is [(1.2, 3), (6.55, 8)]

Linda Over a year ago

No, in the question it is specified: "The output I am looking to get is: output = [(1.2, 3), (6.55, 8)]". The last range is not valid and therefore should not be in the output.

bumblebee Over a year ago

Yes, but lst1[3] and lst2[2] intersect, and their intersection is (24.5, 25)

Ricky Kim Over a year ago

@Linda the problem with your code is that it only compares i-th element of tuples (since you use zip). So if lst1 had (0,0) as first element instead, it will compare it with (1,3) and skip comparison between (1.2,4) with (1,3) and skip all the other points also - giving you an empty list as the solution, which is not correct

Linda Over a year ago

@RickyKim I see, I think I misunderstood the question. I thought the aim was a pair-wise comparison.

|

Andrej Kesely · Accepted Answer · 2019-07-31 14:25:05Z

2

Using itertools and 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)

Prints:

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

answered Jul 31, 2019 at 14:25

Andrej Kesely

196k15 gold badges60 silver badges105 bronze badges

3 Comments

Ricky Kim Over a year ago

This does not find intersection by comparing the two lists but does it by merging which I'm not sure if that's what OP wants. For example, input of lst1 = [(1.2, 4),(1, 3), (5, 8), (19, 21), (24.5, 26)] and lst2 = [(6.55, 14.871), (22, 25)] still outputs the same result, but you might want [(6.55, 8), (24.5, 25)] as output instead.

Ricky Kim Over a year ago

sry I meant lst1 = [(1, 3), (1.2, 4), (5, 8), (19, 21), (24.5, 26)]

Andrej Kesely Over a year ago

@RickyKim Yeah, in this case my script returns [(1.2, 3), (6.55, 8), (24.5, 25)], but it depends on op's input. Maybe ops lists don't have overlapping intervals.

Valentino · Accepted Answer · 2019-07-31 15:23:38Z

A solution using iterators. I use a while loop which stays active until both iterators running on the lists are exausthed.

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)

Using your sample input, this prints: [(1.2, 3), (6.55, 8)]

Junhee Shin · Accepted Answer · 2019-07-31 14:30:45Z

0

make a simple function to get an intersection range for two range.

    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)

and get all intersections though the double loop

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

It would be faster, if you add some conditions in the loop.

edited Jul 31, 2019 at 14:30

answered Jul 31, 2019 at 14:17

Junhee Shin

7586 silver badges8 bronze badges

1 Comment

Ricky Kim Over a year ago

"It would be faster, if you add some conditions in the loop." - then you should add them?

Collectives™ on Stack Overflow

How to find intersections of ranges of float tuples across two lists in python?

4 Answers 4

8 Comments

3 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

8 Comments

3 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related