I have a list that looks like the following
[(100000, 100010), (100005, 100007), (100009, 100015)]
I would like to be able to determine which of these overlap each
other. So, in this case, tuple 1 overlaps with tuples 2 and 3. Tuple
2 overlaps with 1. Tuple 3 overlaps with tuple 1.
In my scenario I would have hundreds, if not thousands of these
ranges. Any nice pythonic way to do this?
Thanks. 7 3167
You should give a more real data set (maybe 20 various pairs so that all
scenarios can be seen) and the output you want.
Breal wrote:
I have a list that looks like the following
[(100000, 100010), (100005, 100007), (100009, 100015)]
I would like to be able to determine which of these overlap each
other. So, in this case, tuple 1 overlaps with tuples 2 and 3. Tuple
2 overlaps with 1. Tuple 3 overlaps with tuple 1.
In my scenario I would have hundreds, if not thousands of these
ranges. Any nice pythonic way to do this?
Thanks.
--
Shane Geiger
IT Director
National Council on Economic Education sg*****@ncee.net | 402-438-8958 | http://www.ncee.net
Leading the Campaign for Economic and Financial Literacy
On Dec 13, 3:45 pm, Breal <sean.be...@cox.netwrote:
I have a list that looks like the following
[(100000, 100010), (100005, 100007), (100009, 100015)]
I would like to be able to determine which of these overlap each
other. So, in this case, tuple 1 overlaps with tuples 2 and 3. Tuple
2 overlaps with 1. Tuple 3 overlaps with tuple 1.
In my scenario I would have hundreds, if not thousands of these
ranges. Any nice pythonic way to do this?
Sure.
Start with a piece of paper and a pencil.
Write down under what conditions two tuples of numbers will overlap.
Be specific.
(Hint: two numbers can be equal, less than, or greater than each
other. That's 3 conditions. Then you can compare the first of the
first tuple to the first of the second tuple, or the first to the
second, or the second to the first, or the second to the second.
That's 4 conditions. 3x4=12 so you have 12 possible conditions when
comparing two tuples of two numbers. Describe what the result should
be for each one. Being graphical will help you get it right.)
Once you have that written down, translate it to python.
In python, write a loop that goes through each item in the list and
compares it to every other item. Remember which items compare
favorably by storing them in a list.
When the loop finishes, you should have a list of all the pairs that
match your conditions.
Since this sounds like a homework assignment, the rest is left as an
exercise to the reader.
On Dec 14, 10:45 am, Breal <sean.be...@cox.netwrote:
I have a list that looks like the following
[(100000, 100010), (100005, 100007), (100009, 100015)]
I would like to be able to determine which of these overlap each
other. So, in this case, tuple 1 overlaps with tuples 2 and 3.
Your definition of overlaps appears to be reflexive, so the following
two results follow automatically.
Tuple
2 overlaps with 1. Tuple 3 overlaps with tuple 1.
In my scenario I would have hundreds, if not thousands of these
ranges. Any nice pythonic way to do this?
Probably not.
Just ensure that (a) your time intervals (start, end) obey start <=
end (b) your list of intervals is sorted, then get stuck in:
# tested no more that what you see
alist = [(100000, 100010), (100005, 100007), (100009, 100015),
(100016, 100017), (100016, 100018)]
n = len(alist)
for i in xrange(n - 1):
istart, iend = alist[i]
for j in xrange(i + 1, n):
jstart, jend = alist[j]
if jstart iend:
break
print "Overlap:", i, alist[i], j, alist[j]
After the sort, it looks like O(N**2) in worst case, but you could get
a few zillion results done while you are hunting for a faster
algorithm.
Cheers,
John
On Dec 13, 5:45 pm, Breal <sean.be...@cox.netwrote:
I have a list that looks like the following
[(100000, 100010), (100005, 100007), (100009, 100015)]
I would like to be able to determine which of these overlap each
other. So, in this case, tuple 1 overlaps with tuples 2 and 3. Tuple
2 overlaps with 1. Tuple 3 overlaps with tuple 1.
In my scenario I would have hundreds, if not thousands of these
ranges. Any nice pythonic way to do this?
What are you going to do with the result? Do you need to know if
there are any overlaps? The number of overlaps? Given any particular
range, what ranges overlap?
There's really no way, other than to compare each range. Note that
the relationship is symmetric, so you can save half you work. A
simple-minded approach might be
---
def overlaps(t1, t2):
return (t2[1] >= t1[0]) and (t2[0] <= t1[1])
in_data = [(100000, 100010), (100005, 100007), (100009, 100015)]
while (len(in_data) 1):
target = in_data.pop(0)
for test in in_data:
if overlaps(target,test):
print "%s overlaps with %s" % (repr(target),repr(test))
---
If you want to save the information for later retrieval, you could
build a dictionary with the ranges as keys:
---
ovr_map = {}
while len(in_data) 1:
target = in_data.pop(0)
for test in in_data:
if overlaps(target,test):
if ovr_map.has_key(target): ovr_map[target].append(test)
else: ovr_map[target] = [test]
if ovr_map.has_key(test): ovr_map[test].append(target)
else: ovr_map[test] = [target]
for target in ovr_map.keys():
for test in ovr_map[target]:
print "%s overlaps with %s" % (repr(target),repr(test))
---
I don't know that there isn't a more Pythonic way, I'm not much of an
expert. HTH,
-=Dave
On Dec 14, 12:05 pm, Dave Hansen <i...@hotmail.comwrote:
On Dec 13, 5:45 pm, Breal <sean.be...@cox.netwrote:
I have a list that looks like the following
[(100000, 100010), (100005, 100007), (100009, 100015)]
I would like to be able to determine which of these overlap each
other. So, in this case, tuple 1 overlaps with tuples 2 and 3. Tuple
2 overlaps with 1. Tuple 3 overlaps with tuple 1.
In my scenario I would have hundreds, if not thousands of these
ranges. Any nice pythonic way to do this?
What are you going to do with the result? Do you need to know if
there are any overlaps? The number of overlaps? Given any particular
range, what ranges overlap?
There's really no way, other than to compare each range. Note that
the relationship is symmetric, so you can save half you work. A
simple-minded approach might be
---
def overlaps(t1, t2):
return (t2[1] >= t1[0]) and (t2[0] <= t1[1])
in_data = [(100000, 100010), (100005, 100007), (100009, 100015)]
while (len(in_data) 1):
target = in_data.pop(0)
A tad excessive:
pop(0) is O(N)
pop() is O(1)
Pythonic and likely to be faster, Take 1:
while in_data:
target = in_data.pop()
Pythonic and likely to be faster, Take 2:
while 1:
try:
target = in_data.pop()
except IndexError:
break
for test in in_data:
if overlaps(target,test):
print "%s overlaps with %s" % (repr(target),repr(test))
Cheers,
John
Hi Breal
I have a list that looks like the following
[(100000, 100010), (100005, 100007), (100009, 100015)]
I would like to be able to determine which of these overlap each
other. So, in this case, tuple 1 overlaps with tuples 2 and 3. Tuple
2 overlaps with 1. Tuple 3 overlaps with tuple 1.
In my scenario I would have hundreds, if not thousands of these
ranges. Any nice pythonic way to do this?
This may be of no help, but....
In 1995 I wrote a C library to do some stuff like this. You're welcome to
the code. It might give you some ideas, or you might want to wrap it for
Python. If you did that, and had additional energy, you could release the
result to the Python community.
As someone said, how/what to do depends what you want to do with the
resulting data structure once you've processed the inputs.
In my case I wanted to be able to read in a large number of ranges and be
able to answer questions like "is X in the range?". I'm pretty sure I made
it possible to add ranges to ignore (i.e., that punch holes in an existing
range). I'm also pretty sure I'd have made this run in n log n time, by
first sorting all the lower bounds (and maybe sorting the upper ones too)
and then walking that list.
One use case is e.g., for a printer program command line:
print --inc-pages 40-70 --exc-pages 51-52 --inc-pages 100-120
which could use the library to step through the range of pages in a doc and
easily check which ones should be printed. There are lots of other uses.
Lookup time on those queries was probably log n where n is the resulting
number of range fragments once the processing (merging/splitting) of the
command line was done.
I don't remember, but it took me several days to write the code, so it
wasn't completely trivial.
I can't offer help beyond the code I'm afraid - I have too much other stuff
going on.
Terry
On 2007-12-14, John Machin <sj******@lexicon.netwrote:
On Dec 14, 10:45 am, Breal <sean.be...@cox.netwrote:
>I have a list that looks like the following [(100000, 100010), (100005, 100007), (100009, 100015)]
I would like to be able to determine which of these overlap each other. So, in this case, tuple 1 overlaps with tuples 2 and 3.
Your definition of overlaps appears to be reflexive, so the following
two results follow automatically.
>Tuple 2 overlaps with 1. Tuple 3 overlaps with tuple 1.
In my scenario I would have hundreds, if not thousands of these ranges. Any nice pythonic way to do this?
Probably not.
Just ensure that (a) your time intervals (start, end) obey start <=
end (b) your list of intervals is sorted, then get stuck in:
# tested no more that what you see
alist = [(100000, 100010), (100005, 100007), (100009, 100015),
(100016, 100017), (100016, 100018)]
n = len(alist)
for i in xrange(n - 1):
istart, iend = alist[i]
for j in xrange(i + 1, n):
jstart, jend = alist[j]
if jstart iend:
break
print "Overlap:", i, alist[i], j, alist[j]
After the sort, it looks like O(N**2) in worst case, but you
could get a few zillion results done while you are hunting for
a faster algorithm.
Simply printing out the list of overlaps, even if you knew, a
priori, that all elements overlapped, is an O(N**2) operation. So
I don't think a better algorithm exists for the worst case.
--
Neil Cerutti
You only get a once-in-a-lifetime opportunity so many times. --Ike Taylor This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: André Søreng |
last post by:
With the re/sre module included with Python 2.4:
pattern = "(?P<id1>avi)|(?P<id2>avi|mp3)"
string2match = "some string with avi in it"
matches = re.finditer(pattern, string2match)
.......
|
by: Max M |
last post by:
I am writing a "find-free-time" function for a calendar. There are a lot
of time spans with start end times, some overlapping, some not.
To find the free time spans, I first need to convert the...
|
by: Phil Sandler |
last post by:
All,
I have a table with start and end dates/times in it, and would like to
be able to calculate the number of hours represented, accounting for
overlapping records.
Note that I am looking...
|
by: Chris Q. |
last post by:
I am creating a custom control that contains a list view with dates and times. I need to make sure that times do not overlap. I would like the control to determine if the overlap is occuring with the...
|
by: giampiero mu |
last post by:
hi everyone
my target is implement a function controlla(string - a binary string-)
that check if there is in a string two equal not overlapping
subsequences at least of length limitem:
my...
|
by: corsin |
last post by:
Hello everybody!
I've been trying to find a way to create a MySQL query to find overlapping intervals, but no success so far. I've the following table as an example:
Src Dst Start_time End_time...
|
by: richard12345 |
last post by:
Hi Guys
I have problem with site I am building. The sidebar with menu and other thinks is overlapping footer. The footer move with the content and but it dos it dos not move with the sidebar. ...
|
by: manugm1987 |
last post by:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<style type="text/css"><!--...
|
by: dcardo |
last post by:
Hi,
I have the following CSS styles:
#legend{
padding: 15px 0px 15px 0px;
font:Georgia, "Times New Roman", Times, serif;
font-size:1.8em;
font-weight:bold;
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
| |