CODEWITHSUNDEEP
pythonalgorithm
mpen
mpen

Reputation: 283355

Given a bunch of ranges of numbers, get all the numbers within those ranges?

In Python, you can get the numbers in a range by calling range(x,y). But given two ranges, say 5-15, and 10-20 how can you get all the numbers 5-20 without duplicates? The ranges may also be disjoint.

I could concat all the results and then uniquify the list, but is that the fastest solution?

Upvotes: 2

Views: 316

Answers (4)

hughdbrown
hughdbrown

Reputation: 49063

>>> a = range(5, 15)
>>> b = range(10, 20)
>>> print sorted(set(a + b))
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Or if you want a more general expansion of the lists to their elements for inclusion in the set:

>>> list_of_lists = [a, b]
>>> print sorted(set(elem for l in list_of_lists for elem in l))
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

And I found a way to compose it all in one line:

>>> list_of_lists = [a, b]
>>> print set.union(*map(set, list_of_lists))

Is sorting necessary? It's just expository, but then I don't see that sets necessarily output in sorted order:

>>> x = set(range(3))
>>> x
set([0, 1, 2])
>>> x.add(-1)
>>> x
set([0, 1, 2, -1])

Upvotes: 9

hughdbrown
hughdbrown

Reputation: 49063

Or you can join overlapping ranges:

>>> def join_overlapping_ranges(ranges):
...     list_of_ranges = []
...     # ranges are sorted on first element
...     for r in sorted(ranges):
...         # ranges are stored as [start, end]
...         if list_of_ranges and list_of_ranges[-1][1] >= r[0]:
...             list_of_ranges[-1][1] = r[1]
...         else:
...             list_of_ranges.append(r)        
...     return list_of_ranges
... 
>>> ranges = [[3,4], [5,7], [1,2], [4,6], [5,5]]
>>> print sorted(ranges)
[[1, 2], [3, 4], [4, 6], [5, 5], [5, 7]]
>>> print join_overlapping_ranges(ranges)
[[1, 2], [3, 7]]

Upvotes: 2

John La Rooy
John La Rooy

Reputation: 304483

For the quantity you need I would just keep it simple

>>> a = range(5, 15)
>>> b = range(10, 20)
>>> from itertools import chain
>>> sorted(set(chain.from_iterable(list_of_lists)))
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Upvotes: 1

IVlad
IVlad

Reputation: 43517

Sort the ranges (x, y) by increasing x values. Now, for each range, if it overlaps the previous range, set your current "big range"'s y value to the current range's y value. If it doesn't, start a new "big range": this one won't overlap any of the previous ones. If the current range is completely included in the current big one, ignore it.

Upvotes: 1

Related Questions