FAQ
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

Search Discussions

  • Arnaud Delobelle at Jan 31, 2008 at 10:16 pm

    On Jan 31, 4:12?pm, erikcw 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),
    (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.iteritems():
    if y != x: yield i, j
    inside[i] = x

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

    --
    Arnaud
  • Thomas Pani at Feb 1, 2008 at 11:23 am

    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.iteritems():
    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
  • Arnaud Delobelle at Feb 1, 2008 at 1:28 pm

    On Feb 1, 11:23?am, Thomas Pani 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 sorted(bounds):
    ? ? ? ? if inside.pop(i, None) is None:
    ? ? ? ? ? ? for j, y in inside.iteritems():
    ? ? ? ? ? ? ? ? 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?
    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 (if it's true!). So if we are in a situation where
    overlaps are rare, it is in practice O(nlogn).

    PS: the way I build 'bounds' is awkward.

    --
    Arnaud
  • Neil Cerutti at Feb 1, 2008 at 2:44 pm

    On Feb 1, 2008 8:28 AM, Arnaud Delobelle 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 (if it's true!). So if we are in a situation where
    overlaps are rare, it is in practice O(nlogn).
    Here's another contender, basically the same as yours, but spelled
    without iterators.

    def overlaps(eranges):
    """Determine, from a list of numbers and a +/- range of uncertainty, which
    number ranges overlap each other. Return the overlapping range indexes as
    a list of overlapping pairs.
    sorted(overlaps(((55, 3), (20, 2), (17, 4), (60, 3))))
    [(0, 3), (1, 2)]
    """
    d = [(r[0] - r[1], r[0] + r[1], i) for i, r in enumerate(eranges)]
    d.sort()
    rv = []
    x = 0
    while x < len(d):
    minx, maxx, ix = d[x]
    y = x+1
    while y < len(d):
    miny, maxy, iy = d[y]
    if miny < maxx:
    rv.append((ix, iy) if ix < iy else (iy, ix))
    else:
    break
    y += 1
    x += 1
    return rv

    --
    Neil Cerutti <mr.cerutti+python at gmail.com>
  • Arnaud Delobelle at Feb 1, 2008 at 7:07 pm

    On Feb 1, 1:28?pm, Arnaud Delobelle 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 (if it's true!). ?So if we are in a situation where
    overlaps are rare, it is in practice O(nlogn).
    I have slightly modified overlaps() in order to make the analysis
    easier (I have made overlaps() consider all intervals open). Here is
    the new version:

    def open_interval(i, (a, b)):
    return (a, 1, i), (b, 0, i)

    def overlaps(lst, interval=open_interval):
    bounds = chain(*starmap(interval, enumerate(lst))) # 1
    inside = {} # 2
    for x, _, i in sorted(bounds): # 3
    if inside.pop(i, None) is None: # 4
    for j, y in inside.iteritems(): yield i, j # 5
    inside[i] = x # 6

    'Detailed' analysis of running overlaps(lst) follows, where

    * lst is of length n
    * the total number of overlaps in m

    (assuming dict.__getitem__ and dic.__setitem__ are done in constant
    time [1])

    1. is a simple loop over lst, takes An
    2. is constant (K)
    3. The sorted(...) function will take Bnlogn
    3,4. This loop is iterated 2n times, with the if condition it will
    take Cn
    5. This loop is iterated once for each overlap exacly. So it will take
    Dm
    6. This statement is executed n times, will take En

    Altogether the time taken is:

    K + (A+B+E)n + Bnlogn + Dm

    So if m is dominated by nlogn, the algorithm is O(nlogn). Otherwise
    one cannot hope for better thant O(m)!

    --
    Arnaud

    [1] Otherwise one could use a combination of an array and a doubly
    linked list to achieve constant time access, deletion and updating of
    the 'inside' structure. Anyway even if it was log(n) the overall
    complexity would be the same!
  • Arnaud Delobelle at Feb 1, 2008 at 8:16 pm

    On Feb 1, 2:44?pm, "Neil Cerutti" wrote:
    On Feb 1, 2008 8:28 AM, Arnaud Delobelle 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 (if it's true!). ?So if we are in a situation where
    overlaps are rare, it is in practice O(nlogn).
    Here's another contender, basically the same as yours, but spelled
    without iterators.

    def overlaps(eranges):
    ? ? """Determine, from a list of numbers and a +/- range of uncertainty, which
    ? ? number ranges overlap each other. Return the overlapping range indexes as
    ? ? a list of ?overlapping pairs.

    ? ? >>> sorted(overlaps(((55, 3), (20, 2), (17, 4), (60, 3))))
    ? ? [(0, 3), (1, 2)]
    ? ? """
    ? ? d = [(r[0] - r[1], r[0] + r[1], i) for i, r in enumerate(eranges)]
    ? ? d.sort()
    ? ? rv = []
    ? ? x = 0
    ? ? while x < len(d):
    ? ? ? ? minx, maxx, ix = d[x]
    ? ? ? ? y = x+1
    ? ? ? ? while y < len(d):
    ? ? ? ? ? ? miny, maxy, iy = d[y]
    ? ? ? ? ? ? if miny < maxx:
    ? ? ? ? ? ? ? ? rv.append((ix, iy) if ix < iy else (iy, ix))
    ? ? ? ? ? ? else:
    ? ? ? ? ? ? ? ? break
    ? ? ? ? ? ? y += 1
    ? ? ? ? x += 1
    ? ? return rv
    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. See my other post for a 'detailed' analysis of my solution.

    --
    Arnaud
  • Neil Cerutti at Feb 1, 2008 at 8:34 pm

    On Feb 1, 2008 3:16 PM, Arnaud Delobelle wrote:
    On Feb 1, 2:44 pm, "Neil Cerutti" wrote:
    Here's another contender, basically the same as yours, but spelled
    without iterators.

    def overlaps(eranges):
    """Determine, from a list of numbers and a +/- range of uncertainty, which
    number ranges overlap each other. Return the overlapping range indexes as
    a list of overlapping pairs.
    sorted(overlaps(((55, 3), (20, 2), (17, 4), (60, 3))))
    [(0, 3), (1, 2)]
    """
    d = [(r[0] - r[1], r[0] + r[1], i) for i, r in enumerate(eranges)]
    d.sort()
    rv = []
    x = 0
    while x < len(d):
    minx, maxx, ix = d[x]
    y = x+1
    while y < len(d):
    miny, maxy, iy = d[y]
    if miny < maxx:
    rv.append((ix, iy) if ix < iy else (iy, ix))
    else:
    break
    y += 1
    x += 1
    return rv
    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. See my other post for a 'detailed' analysis of my solution.
    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.

    --
    Neil Cerutti <mr.cerutti+python at gmail.com>
  • Arnaud Delobelle at Feb 1, 2008 at 9:13 pm

    On Feb 1, 8:34?pm, "Neil Cerutti" wrote:
    On Feb 1, 2008 3:16 PM, Arnaud Delobelle 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 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
  • Boris Borcic at Feb 8, 2008 at 1:48 pm
    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
  • Boris Borcic at Feb 8, 2008 at 2:08 pm

    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))
  • Arnaud Delobelle at Feb 8, 2008 at 4:06 pm

    On Feb 8, 1:48?pm, 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))

    Cheers, BB
    I did mention that it was awkward (but at the time I just wrote what
    came to mind) - thank you for providing a much improved version.

    It doesn't deter from the fact that the algorithm is of optimal
    complexity (modulo sorting of the list).

    --
    Arnaud
  • Attn Steven Kuo at Jan 31, 2008 at 10:48 pm

    On Jan 31, 8:12 am, erikcw 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),
    (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(mysets):
    for next_idx, next_s in enumerate(mysets[idx+1:]):
    if s.intersection(next_s):
    print "mylist[%d] and mylist[%d] intersect" % (
    idx, idx + next_idx + 1 )


    --
    Hope this helps,
    Steve
  • Attn Steven Kuo at Jan 31, 2008 at 10:58 pm

    On Jan 31, 2:48 pm, "attn.steven.... at gmail.com" wrote:
    On Jan 31, 8:12 am, erikcw 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.intersection(next_s):
    print "mylist[%d] and mylist[%d] intersect" % (
    idx, idx + next_idx + 1 )

    Um, that would have been more helpful if I hadn't forgotten
    to preface that with:

    mylist = [(55, 58, 52), (20, 22, 18), (17, 21, 13), (60, 63, 57),]
    mysets = [set(range(x[2],x[1])) for x in mylist]

    --
    Cheers,
    Steven
  • Attn Steven Kuo at Jan 31, 2008 at 11:24 pm

    On Jan 31, 3:09 pm, Paul Rubin wrote:
    "attn.steven.... at gmail.com" <attn.steven.... at gmail.com> 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 1000000, you get a set with
    a million elements.


    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.

    xset?

    --
    Regards,
    Steven
  • George Sakkis at Feb 1, 2008 at 1:34 am

    On Jan 31, 7:11 pm, Paul Rubin wrote:
    "attn.steven.... at gmail.com" <attn.steven.... at gmail.com> 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 way, that solves the space problem
    but leaves a speed problem. You probably want to use something like
    sort the intervals and then use the bisect module to find the
    intervals intersecting a given one.
    I haven't actually used it but from the short description this package
    seems to fit the bill: http://pypi.python.org/pypi/interval/1.0.0

    George
  • Matthew_WARREN at Feb 1, 2008 at 12:54 pm
    Internet
    attn.steven.kuo at gmail.com
    To
    python-list
    Sent by: cc
    python-list-bounces+matthew.warren=uk.bnpparibas.com@
    python.org Subject
    Re: How to identify which numbers in a list are within each others'
    31/01/2008 22:48 range














    On Jan 31, 8:12 am, erikcw 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),
    (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.
    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),(17,21,13),(60,63,57)]
    a=[ (l[2],l[1]) for l in lst ]
    a.sort()
    a=[(1,5),(4,9),(10,12),(11,15),(16,19)]

    i=[ (pair,a[a.index(pair)+1]) for pair in a[:-1] if
    a[a.index(pair)+1][0]<pair[1]]
    i
    [((13, 21), (18, 22)), ((52, 58), (57, 63))]

    ?

    Matt.


    This message and any attachments (the "message") is
    intended solely for the addressees and is confidential.
    If you receive this message in error, please delete it and
    immediately notify the sender. Any use not in accord with
    its purpose, any dissemination or disclosure, either whole
    or partial, is prohibited except formal approval. The internet
    can not guarantee the integrity of this message.
    BNP PARIBAS (and its subsidiaries) shall (will) not
    therefore be liable for the message if modified.
    Do not print this message unless it is necessary,
    consider the environment.

    ---------------------------------------------

    Ce message et toutes les pieces jointes (ci-apres le
    "message") sont etablis a l'intention exclusive de ses
    destinataires et sont confidentiels. Si vous recevez ce
    message par erreur, merci de le detruire et d'en avertir
    immediatement l'expediteur. Toute utilisation de ce
    message non conforme a sa destination, toute diffusion
    ou toute publication, totale ou partielle, est interdite, sauf
    autorisation expresse. L'internet ne permettant pas
    d'assurer l'integrite de ce message, BNP PARIBAS (et ses
    filiales) decline(nt) toute responsabilite au titre de ce
    message, dans l'hypothese ou il aurait ete modifie.
    N'imprimez ce message que si necessaire,
    pensez a l'environnement.
  • Matthew_WARREN at Feb 1, 2008 at 1:00 pm

    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),(17,21,13),(60,63,57)]
    a=[ (l[2],l[1]) for l in lst ]
    a.sort()
    a=[(1,5),(4,9),(10,12),(11,15),(16,19)]
    i=[ (pair,a[a.index(pair)+1]) for pair in a[:-1] if
    a[a.index(pair)+1][0]<pair[1]]
    i
    [((13, 21), (18, 22)), ((52, 58), (57, 63))]
    ?
    Ah.

    I guess not. That attempt doesnt catch non adjacent ranges that also
    overlap :/

    Matt.


    This message and any attachments (the "message") is
    intended solely for the addressees and is confidential.
    If you receive this message in error, please delete it and
    immediately notify the sender. Any use not in accord with
    its purpose, any dissemination or disclosure, either whole
    or partial, is prohibited except formal approval. The internet
    can not guarantee the integrity of this message.
    BNP PARIBAS (and its subsidiaries) shall (will) not
    therefore be liable for the message if modified.
    Do not print this message unless it is necessary,
    consider the environment.

    ---------------------------------------------

    Ce message et toutes les pieces jointes (ci-apres le
    "message") sont etablis a l'intention exclusive de ses
    destinataires et sont confidentiels. Si vous recevez ce
    message par erreur, merci de le detruire et d'en avertir
    immediatement l'expediteur. Toute utilisation de ce
    message non conforme a sa destination, toute diffusion
    ou toute publication, totale ou partielle, est interdite, sauf
    autorisation expresse. L'internet ne permettant pas
    d'assurer l'integrite de ce message, BNP PARIBAS (et ses
    filiales) decline(nt) toute responsabilite au titre de ce
    message, dans l'hypothese ou il aurait ete modifie.
    N'imprimez ce message que si necessaire,
    pensez a l'environnement.
  • Karthik Gurusamy at Feb 1, 2008 at 8:17 pm

    On Jan 31, 8:12 am, erikcw 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),
    (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(strips_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(node)
    return edges

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

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

    Karthik
    Thanks!
    Erik
  • Arnaud Delobelle at Feb 1, 2008 at 8:28 pm
    On Feb 1, 8:17?pm, Karthik Gurusamy 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', i)) for i,s in
    enumerate(strips_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(node)
    ? ? return edges
    Interesting. This is a long version of the algorithm I posted
    earlier.

    --
    Arnaud
  • Paul McGuire at Feb 8, 2008 at 3:20 pm

    On Jan 31, 10:12?am, erikcw 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:

    --XXX-----XXXXXXXXX----XXXXXX-------
    --------XXXX------------------------

    I test the overlapping by drawing a line from the min of the lower
    range to the max of each upper range, and from the max of the lower
    range to the min of each upper range. Overlap occurs if one delta is
    positive and the other negative. Multiply the two deltas, and overlap
    occurs if the product is negative. If ranges are inclusive instead of
    exclusive of the bounds, then a 0 product also counts as overlap.

    # don't name variables 'list' or 'dict' or 'int' or 'str' or 'tuple'
    ranges = [
    (55, 58, 52),
    (20, 22, 18),
    (17, 21, 13),
    (60, 63, 57),
    ]

    def overlap(r1, r2):
    _,max1,min1 = r1
    _,max2,min2 = r2
    # if max1==min2 or max2==min1 counts as overlap, change '<' to
    '<='
    return (max2-min1)*(min2-max1) < 0

    for i,r1 in enumerate(ranges[:-1]):
    for r2 in ranges[i+1:]:
    if overlap(r1,r2):
    print r1, "overlaps", r2
    else:
    print r1, "does not overlap", r2

    Prints:
    (55, 58, 52) does not overlap (20, 22, 18)
    (55, 58, 52) does not overlap (17, 21, 13)
    (55, 58, 52) overlaps (60, 63, 57)
    (20, 22, 18) overlaps (17, 21, 13)
    (20, 22, 18) does not overlap (60, 63, 57)
    (17, 21, 13) does not overlap (60, 63, 57)


    -- Paul

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppython-list @
categoriespython
postedJan 31, '08 at 4:12p
activeFeb 8, '08 at 4:06p
posts21
users10
websitepython.org

People

Translate

site design / logo © 2022 Grokbase