Combining python multiple ranges

Question

I have these ranges:

7,10 11,13 11,15 14,20 23,39 

I need to combine overlapping ranges to give ranges that do not overlap, so in the example:

 7,20 23,39 

I did this in Ruby, where I clicked the beginning and end of a range in an array and sorted them, and then merged the overlapping ranges. Any quick way to do this in Python?

thanks

Answer 1

Say (7, 10) and (11, 13) lead to (7, 13) :

 a = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)] b = [] for begin,end in sorted(a): if b and b[-1][1] >= begin - 1: b[-1] = (b[-1][0], end) else: b.append((begin, end)) 

b now

 [(7, 20), (23, 39)] 

EDIT

As @CentAu correctly points out, [(2,4), (1,6)] will return (1,4) instead of (1,6) . Here is the new version with the correct handling of this case:

 a = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)] b = [] for begin,end in sorted(a): if b and b[-1][1] >= begin - 1: b[-1][1] = max(b[-1][1], end) else: b.append([begin, end]) 

Answer 2

Old question. But I would like to add this answer for future references. sympy can be used to combine intervals:

 from sympy import Interval, Union def union(data): """ Union of a list of intervals eg [(1,2),(3,4)] """ intervals = [Interval(begin, end) for (begin, end) in data] u = Union(*intervals) return [list(u.args[:2])] if isinstance(u, Interval) \ else list(u.args) 

If the Union output exceeds two intervals, this is a Union object, and when there is one interval, the output is an Interval object. This is the reason for the if statement in the return line.

examples:

 In [26]: union([(10, 12), (14, 16), (15, 22)]) Out[26]: [[10, 12], [14, 22]] In [27]: union([(10, 12), (9, 16)]) Out[27]: [[9, 16]] 

Answer 3

I tried with special cases of the presence of (45, 46) and (45, 45)
as well as test cases that are unlikely to occur in your application: presence (11.6), presence (-1, -5), presence (-9, 5), presence (-3, 10). <w> In any case, the results are suitable for all these cases, this is the point.

Algorithm:

 def yi(li): gen = (x for a,b in li for x in xrange(a,b+1)) start = p = gen.next() for x in gen: if x>p+2: yield (start,p) start = p = x else: p = x yield (start,x) 

If aff in the following code is set to True, the steps will be shown.

 def yi(li): aff = 0 gen = (x for a,b in li for x in xrange(a,b+1)) start = p = gen.next() for x in gen: if aff: print ('start %sp %d p+2 %d ' 'x==%s' % (start,p,p+2,x)) if x>p+2: if aff: print 'yield range(%d,%d)' % (start,p+1) yield (start,p) start = p = x else: p = x if aff: print 'yield range(%d,%d)' % (start,x+1) yield (start,x) for li in ([(7,10),(23,39),(11,13),(11,15),(14,20),(45,46)], [(7,10),(23,39),(11,13),(11,15),(14,20),(45,46),(45,45)], [(7,10),(23,39),(11,13),(11,15),(14,20),(45,45)], [(7,10),(23,39),(11,13),(11,6),(14,20),(45,46)], #1 presence of (11, 6) [(7,10),(23,39),(11,13),(-1,-5),(14,20),(45,45)], #2 presence of (-1,-5) [(7,10),(23,39),(11,13),(-9,-5),(14,20),(45,45)], #3 presence of (-9, -5) [(7,10),(23,39),(11,13),(-3,10),(14,20),(45,45)]): #4 presence of (-3, 10) li.sort() print 'sorted li %s'%li print '\n'.join(' (%d,%d) %r' % (a,b,range(a,b)) for a,b in li) print 'list(yi(li)) %s\n' % list(yi(li)) 

result

 sorted li [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39), (45, 46)] (7,10) [7, 8, 9] (11,13) [11, 12] (11,15) [11, 12, 13, 14] (14,20) [14, 15, 16, 17, 18, 19] (23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38] (45,46) [45] list(yi(li)) [(7, 20), (23, 39), (45, 46)] sorted li [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39), (45, 45), (45, 46)] (7,10) [7, 8, 9] (11,13) [11, 12] (11,15) [11, 12, 13, 14] (14,20) [14, 15, 16, 17, 18, 19] (23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38] (45,45) [] (45,46) [45] list(yi(li)) [(7, 20), (23, 39), (45, 46)] sorted li [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39), (45, 45)] (7,10) [7, 8, 9] (11,13) [11, 12] (11,15) [11, 12, 13, 14] (14,20) [14, 15, 16, 17, 18, 19] (23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38] (45,45) [] list(yi(li)) [(7, 20), (23, 39), (45, 45)] sorted li [(7, 10), (11, 6), (11, 13), (14, 20), (23, 39), (45, 46)] (7,10) [7, 8, 9] (11,6) [] (11,13) [11, 12] (14,20) [14, 15, 16, 17, 18, 19] (23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38] (45,46) [45] list(yi(li)) [(7, 20), (23, 39), (45, 46)] sorted li [(-1, -5), (7, 10), (11, 13), (14, 20), (23, 39), (45, 45)] (-1,-5) [] (7,10) [7, 8, 9] (11,13) [11, 12] (14,20) [14, 15, 16, 17, 18, 19] (23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38] (45,45) [] list(yi(li)) [(7, 20), (23, 39), (45, 45)] sorted li [(-9, -5), (7, 10), (11, 13), (14, 20), (23, 39), (45, 45)] (-9,-5) [-9, -8, -7, -6] (7,10) [7, 8, 9] (11,13) [11, 12] (14,20) [14, 15, 16, 17, 18, 19] (23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38] (45,45) [] list(yi(li)) [(-9, -5), (7, 20), (23, 39), (45, 45)] sorted li [(-3, 10), (7, 10), (11, 13), (14, 20), (23, 39), (45, 45)] (-3,10) [-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (7,10) [7, 8, 9] (11,13) [11, 12] (14,20) [14, 15, 16, 17, 18, 19] (23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38] (45,45) [] list(yi(li)) [(-3, 20), (23, 39), (45, 45)] 

Answer 4

The following function works well with:

<h3> a = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)]

and

a = [(2,4), (1,6)]

 def range_overlap_adjust(list_ranges): overlap_corrected = [] for start, stop in sorted(list_ranges): if overlap_corrected and start-1 <= overlap_corrected [-1][1] and stop >= overlap_corrected [-1][1]: overlap_corrected [-1] = min(overlap_corrected [-1][0], start), stop elif overlap_corrected and start <= overlap_corrected [-1][1] and stop <= overlap_corrected [-1][1]: break else: overlap_corrected.append((start,stop)) return overlap_corrected 

Test

 list_ranges = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)] print range_overlap_adjust(list_ranges) 

gives:

[(7, 20), (23, 39)]