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

On Feb 8, 1:48 pm, Boris Borcic <[EMAIL PROTECTED]> 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 > >        bou

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

On Jan 31, 10:12 am, erikcw <[EMAIL PROTECTED]> wrote: > Hi, > > I have a list of numbers each with a +/- margin of error.  I need to > identify which ones overlab each other. > Here's my proposal, using arithmetic instead of sets. Looking at the problem graphically, I drew different numberlines:

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

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

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

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 -- http:

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

On Feb 1, 8:34 pm, "Neil Cerutti" <[EMAIL PROTECTED]> wrote: > On Feb 1, 2008 3:16 PM, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > > 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

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

On Feb 1, 2008 3:16 PM, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > On Feb 1, 2:44 pm, "Neil Cerutti" <[EMAIL PROTECTED]> wrote: > > Here's another contender, basically the same as yours, but spelled > > without iterators. > > > > def overlaps(eranges): > > """Determine, from a list of number

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

On Feb 1, 8:17 pm, Karthik Gurusamy <[EMAIL PROTECTED]> wrote: [...] > 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',

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

On Jan 31, 8:12 am, erikcw <[EMAIL PROTECTED]> wrote: > 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),

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

On Feb 1, 2:44 pm, "Neil Cerutti" <[EMAIL PROTECTED]> wrote: > On Feb 1, 2008 8:28 AM, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > > > Yours  is O(n^2) and \Omega(n^2).  I think mine is O(max(c, nlogn)) > > (assuming constant time access for dictionaries, but 'inside' could be > > replaced with a

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

On Feb 1, 1:28 pm, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > Yours  is O(n^2) and \Omega(n^2).  I think mine is O(max(c, nlogn)) > (assuming constant time access for dictionaries, but 'inside' could be > replaced with a list) where c is the number of overlaps.  I'll try to > post a proof later

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

On Feb 1, 2008 8:28 AM, Arnaud Delobelle <[EMAIL PROTECTED]> wrote: > Yours is O(n^2) and \Omega(n^2). I think mine is O(max(c, nlogn)) > (assuming constant time access for dictionaries, but 'inside' could be > replaced with a list) where c is the number of overlaps. I'll try to > post a proof l

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

On Feb 1, 11:23 am, Thomas Pani <[EMAIL PROTECTED]> wrote: > 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 s

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

>> 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. >> >Is this usable? >Assuming you transform your 3 tuples into a list of start-end 2 tuples and sort them for lowest to highest, then >lst=[(55,58,52),(20,22,18

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

Internet

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

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: >

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

On Jan 31, 7:11 pm, Paul Rubin wrote: > "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> writes: > > True... Any lighter-weight implementation of > > sets out there? That is, one that would defer > > use of resources until actually needed -- > > somewhat akin to the distinction

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

"[EMAIL PROTECTED]" <[EMAIL PROTECTED]> writes: > True... Any lighter-weight implementation of > sets out there? That is, one that would defer > use of resources until actually needed -- > somewhat akin to the distinction between > range and xrange, and so on. Don't even think of doing it that w

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

On Jan 31, 3:09 pm, Paul Rubin wrote: > "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> writes: > > mysets = [set(range(x[2],x[1])) for x in mylist] > > This is pretty horrible, each set can be arbitrarily large, > i.e. if x[2] and x[1] are 0 and 100, you get a set with > a m

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

"[EMAIL PROTECTED]" <[EMAIL PROTECTED]> writes: > mysets = [set(range(x[2],x[1])) for x in mylist] This is pretty horrible, each set can be arbitrarily large, i.e. if x[2] and x[1] are 0 and 100, you get a set with a million elements. -- http://mail.python.org/mailman/listinfo/python-list

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

On Jan 31, 2:48 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote: > On Jan 31, 8:12 am, erikcw <[EMAIL PROTECTED]> wrote: > > One way would be to use sets and check for intersection: > > for idx, s in enumerate(mysets): > for next_idx, next_s in enumerate(mysets[idx+1:]): > if s.inter

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

On Jan 31, 8:12 am, erikcw <[EMAIL PROTECTED]> wrote: > 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),

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

On Jan 31, 4:12 pm, erikcw <[EMAIL PROTECTED]> wrote: > 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),

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

erikcw <[EMAIL PROTECTED]> writes: > 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 inter

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