473,856 Members | 1,630 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

How to identify which numbers in a list are within each others' range

Hi,

I have a list of numbers each with a +/- margin of error. I need to
identify which ones overlab each other.

For example:
55 +/- 3
20 +/- 2
17 +/- 4
60 +/- 3

#base, max, min
list = [
(55, 58, 52),
(20, 22, 18),
(17, 21, 13),
(60, 63, 57),
]

In this example the range of list[0] overlaps the range of list[3] AND
list[1] overlaps list[2]

What is the best way to in python to identify the list items that
overlap and the items that don't overlap with any other.

Thanks!
Erik
Jan 31 '08 #1
10 2282
erikcw <er***********@ gmail.comwrites :
What is the best way to in python to identify the list items that
overlap and the items that don't overlap with any other.
This sounds like a homework problem, so the first thing I'll suggest
is that you figure out exactly what it means for two of those
intervals to overlap. That should let you write a simple program that
gets the right answer, but that can run slowly if the number of lists
gets large. The next thing to do after that is figure out how to
speed it up, if necessary. But do the first part first.
Jan 31 '08 #2
On Jan 31, 4:12*pm, erikcw <erikwickst...@ gmail.comwrote:
Hi,

I have a list of numbers each with a +/- margin of error. *I need to
identify which ones overlab each other.

For example:
55 +/- 3
20 +/- 2
17 +/- 4
60 +/- 3

#base, max, min
list = [
(55, 58, 52),
(20, 22, 18),
(17, 21, 13),
(60, 63, 57),
]

In this example the range of list[0] overlaps the range of list[3] AND
list[1] overlaps list[2]

What is the best way to in python to identify the list items that
overlap and the items that don't overlap with any other.
This is definitely the best way:

=============== ========
lst = [
(55, 58, 52),
(20, 22, 18),
(17, 21, 13),
(60, 63, 57),
]

from itertools import chain

def overlaps(lst):
bounds = chain(*(((x[1],i), (x[2], i)) for i,x in enumerate(lst)) )
inside = {}
for x, i in sorted(bounds):
if inside.pop(i, None) is None:
for j, y in inside.iteritem s():
if y != x: yield i, j
inside[i] = x

=============== ===============
>>list(overlaps (lst))
[(1, 2), (3, 0)]

--
Arnaud

Jan 31 '08 #3
On Jan 31, 8:12 am, erikcw <erikwickst...@ gmail.comwrote:
Hi,

I have a list of numbers each with a +/- margin of error. I need to
identify which ones overlab each other.

For example:
55 +/- 3
20 +/- 2
17 +/- 4
60 +/- 3

#base, max, min
list = [
(55, 58, 52),
(20, 22, 18),
(17, 21, 13),
(60, 63, 57),
]

In this example the range of list[0] overlaps the range of list[3] AND
list[1] overlaps list[2]

What is the best way to in python to identify the list items that
overlap and the items that don't overlap with any other.

One way would be to use sets and check for intersection:

for idx, s in enumerate(myset s):
for next_idx, next_s in enumerate(myset s[idx+1:]):
if s.intersection( next_s):
print "mylist[%d] and mylist[%d] intersect" % (
idx, idx + next_idx + 1 )
--
Hope this helps,
Steve


Jan 31 '08 #4
Arnaud Delobelle wrote:
>
This is definitely the best way:

from itertools import chain

def overlaps(lst):
bounds = chain(*(((x[1],i), (x[2], i)) for i,x in enumerate(lst)) )
inside = {}
for x, i in sorted(bounds):
if inside.pop(i, None) is None:
for j, y in inside.iteritem s():
if y != x: yield i, j
inside[i] = x
Why not just

def overlaps(lst):
for i,x in enumerate(lst):
for j,y in enumerate(lst):
if i != j and x[1] y[2] x[2]:
yield i,j

It's still n^2. Or am I missing something?

Cheers,
thomas
Feb 1 '08 #5
On Jan 31, 8:12 am, erikcw <erikwickst...@ gmail.comwrote:
Hi,

I have a list of numbers each with a +/- margin of error. I need to
identify which ones overlab each other.

For example:
55 +/- 3
20 +/- 2
17 +/- 4
60 +/- 3

#base, max, min
list = [
(55, 58, 52),
(20, 22, 18),
(17, 21, 13),
(60, 63, 57),
]

In this example the range of list[0] overlaps the range of list[3] AND
list[1] overlaps list[2]

What is the best way to in python to identify the list items that
overlap and the items that don't overlap with any other.
Note you just need the left-end and right-end of each interval. Mean
is redundant information. Once you sort the interval, you can just go
from left to right, retaining only necessary information.

Below method is O(n log n) + O (nk) where k is the average overlaps
per interval.
On most average case, first term dominates and hence its O(n log n);
worst case is ofcourse O(n^2) (a simple case is all n intervals
overlapping with each other)
def strip_sort (a, b):
if a[0] < b[0]:
return -1
if a[0] b[0]:
return 1
# To allow overlaps on a point, return L first then R
# If overlap on a point must not be allowed, return 1 below
if a[0] == 'L': return -1
return 0

def overlaps (strips_given):
# split each interval into two items. basically decorate with 'L'
for left-end of the interval, 'R' for right end of the interval
s2 = [((s[0], 'L', i) , (s[1], 'R', i)) for i,s in
enumerate(strip s_given)]
strips = []
for s in s2: # flatten out the tuples
strips.append(s[0])
strips.append(s[1])

clique = set() # set of nodes where each overlap with everyone
else in the set
edges = [] # we are constructing a graph on N nodes where edge
i,j implies i and j overlap
# below is O(N log N) where is N is number of intervals
strips.sort(cmp =strip_sort)
for s in strips:
node = s[2]
if s[1] == 'L':
clique.add(node )
if s[1] == 'R':
# below is O(k) where k is clique size (overlaps per
interval)
new_edges = [(node, i) for i in clique if i != node]
edges += new_edges
clique.remove(n ode)
return edges

def main():
lst = [(52, 58), (18, 22), (13, 21), (57, 63)]
print overlaps(lst)

Output:
[(2, 1), (0, 3)]

Karthik
>
Thanks!
Erik
Feb 1 '08 #6
On Feb 1, 8:17*pm, Karthik Gurusamy <kar1...@gmail. comwrote:
[...]
def strip_sort (a, b):
* * if a[0] < b[0]:
* * * * return -1
* * if a[0] b[0]:
* * * * return 1
* * if a[0] == 'L': return -1
* * return 0

def overlaps (strips_given):
* * s2 = [((s[0], 'L', i) , (s[1], 'R', i)) for i,s in
enumerate(strip s_given)]
* * strips = []
* * for s in s2:
* * * * strips.append(s[0])
* * * * strips.append(s[1])
* * clique = set()
* * edges = []
* * strips.sort(cmp =strip_sort)
* * for s in strips:
* * * * node = s[2]
* * * * if s[1] == 'L':
* * * * * * clique.add(node )
* * * * if s[1] == 'R':
* * * * * * new_edges = [(node, i) for i in clique if i !=node]
* * * * * * edges += new_edges
* * * * * * clique.remove(n ode)
* * return edges
Interesting. This is a long version of the algorithm I posted
earlier.

--
Arnaud

Feb 1 '08 #7
On Feb 1, 8:34*pm, "Neil Cerutti" <mr.ceru...@gma il.comwrote:
On Feb 1, 2008 3:16 PM, Arnaud Delobelle <arno...@google mail.comwrote:
The total number of iterations is 1+2+...+n = n(n+1)/2 (when n is the
number of intervals) so this has quadratic behaviour regardless of
input.[...]
But it breaks out of the inner loop as soon as ranges on the right
cannot overlap. The loop is O(N) for all input if I define N as
"number of overlaps", a pretty reasonable definition--it's madness to
expect to report N overlaps with less than N complexity.

Unless I'm making a silly mistake. Again.
No you're not mistaken, I am. I didn't see the 'else: break' bit
which of course makes all the difference. Sorry...

On the point of complexity though, it is only O(N) is N dominates
nlogn (n being the length of input).

--
Arnaud

Feb 1 '08 #8
Arnaud Delobelle wrote:
(...)
>
from itertools import chain

def overlaps(lst):
bounds = chain(*(((x[1],i), (x[2], i)) for i,x in enumerate(lst)) )
imho, this is a uselessly painful equivalent of

bounds = ((x[k],i) for i,x in enumerate(lst) for k in (1,2))

Cheers, BB
Feb 8 '08 #9
Boris Borcic wrote:
Arnaud Delobelle wrote:
(...)
>>
from itertools import chain

def overlaps(lst):
bounds = chain(*(((x[1],i), (x[2], i)) for i,x in enumerate(lst)) )

imho, this is a uselessly painful equivalent of

bounds = ((x[k],i) for i,x in enumerate(lst) for k in (1,2))
even more readable :

bounds = ((bound(x),i) for bound in (min,max) for i,x in enumerate(lst))
Feb 8 '08 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
10527
by: Leif K-Brooks | last post by:
I'm a newbie at C++, but no stranger to other programming languages. I'm working on my first C++ program (besides "hello world" and the like), and it needs to generate a (pseudo-)random number between 1 and 10. What would be the simplest way to do that? All of the libraries I found on Google seemed to be made for rocket scientists.
5
14904
by: BlackFireNova | last post by:
I need to write a report in which one part shows a count of how many total records fall within the working days (Monday - Friday) inside of a (prompted) given date range, in a particular geographical region. I have written a query which prompts the user for the start and end dates. It also filters for entries which pertain to the particular geographical region. I'm not sure where to go from here.
3
3285
by: Stewart Allen | last post by:
Hi there I'm trying to find part serial numbers between 2 numbers. The user selects a part number from a combo box and then enters a range of serial numbers into 2 text boxes and the resulting query should find every machine that has that part number between the serial number range. The problem is that the serial number stored is a text field and the results are not what they should be.
28
2603
by: Elfour | last post by:
In c++ what is the code to make teh program randomly select a number?
2
4216
by: shihaoran | last post by:
I really need help with one my program; it is about arraylist; I do not get it. Can someone please help me with it? Here's the instruction: 1. Your instructor will provide you with a text file, (numbers.txt), containing a large (N <= 1000) number of integers. The integers range in value from 0 to 100. The text file has been created with one value on each line. Due to the potential for the sum of the numbers to be very large, you...
13
2822
by: Peter Oliphant | last post by:
I would like to be able to create a random number generator that produces evenly distributed random numbers up to given number. For example, I would like to pick a random number less than 100000, or between 0 and 99999 (inclusive). Further, the I want the range to be a variable. Concretely, I would like to create the following method: unsigned long Random( unsigned long num )
26
7932
by: bilgekhan | last post by:
What is the correct method for generating 2 independent random numbers? They will be compared whether they are equal. What about this method: srand(time(0)); int r1 = rand(); srand(rand()); int r2 = rand(); bool f = r1 == r2;
3
1260
by: djcamo | last post by:
Hi, I have a situation where I have a collection that holds numbers. Mostly they are concurrent eg. 125801-125899 but sometimes they are not eg. 125801-125899, 195301-399. Is there any way to split the numbers and create another collection based on where the numbers change, that is one colletion for the 125801-125899 range and another for the 195301-399 range. Any help much appreciated.
33
12241
by: Andreas Prilop | last post by:
To get bold numbers in ordered lists, one can write ol { font-weight: bold } ol span { font-weight: normal } <ol> <li><span>......</span></li> <li><span>......</span></li> </ol>
0
9916
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
11057
Oralloy
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, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10696
jinu1996
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 tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10782
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9531
agi2029
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, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5958
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4575
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4174
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3201
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.