Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Is a merge interval function available?

Reply
Thread Tools

Is a merge interval function available?

 
 
Peng Yu
Guest
Posts: n/a
 
      02-10-2010
I'm wondering there is already a function in python library that can
merge intervals. For example, if I have the following intervals ('['
and ']' means closed interval as in
http://en.wikipedia.org/wiki/Interva..._the_endpoints)

[1, 3]
[2, 9]
[10,13]
[11,12]

I want to get the following merged intervals.

[1,9]
[10,13]

Could somebody let me know if there is a function in the python
library?
 
Reply With Quote
 
 
 
 
Steven D'Aprano
Guest
Posts: n/a
 
      02-11-2010
On Wed, 10 Feb 2010 15:23:42 -0800, Peng Yu wrote:

> I'm wondering there is already a function in python library that can
> merge intervals. For example, if I have the following intervals ('[' and
> ']' means closed interval as in
> http://en.wikipedia.org/wiki/Interval_(mathematics)

#Excluding_the_endpoints)

Not in the standard library. There may be third-party libraries that do
it. Did you google "python interval"?




--
Steven
 
Reply With Quote
 
 
 
 
Nobody
Guest
Posts: n/a
 
      02-11-2010
On Wed, 10 Feb 2010 15:23:42 -0800, Peng Yu wrote:

> I'm wondering there is already a function in python library that can
> merge intervals. For example, if I have the following intervals ('['
> and ']' means closed interval as in
> http://en.wikipedia.org/wiki/Interva..._the_endpoints)
>
> [1, 3]
> [2, 9]
> [10,13]
> [11,12]
>
> I want to get the following merged intervals.
>
> [1,9]
> [10,13]
>
> Could somebody let me know if there is a function in the python
> library?


No, but try this:

def merge(intervals):
if not intervals:
return []
intervals = sorted(intervals, key = lambda x: x[0])
result = []
(a, b) = intervals[0]
for (x, y) in intervals[1:]:
if x <= b:
b = max(b, y)
else:
result.append((a, b))
(a, b) = (x, y)
result.append((a, b))
return result

 
Reply With Quote
 
Steve Holden
Guest
Posts: n/a
 
      02-11-2010
Nobody wrote:
> On Wed, 10 Feb 2010 15:23:42 -0800, Peng Yu wrote:
>
>> I'm wondering there is already a function in python library that can
>> merge intervals. For example, if I have the following intervals ('['
>> and ']' means closed interval as in
>> http://en.wikipedia.org/wiki/Interva..._the_endpoints)
>>
>> [1, 3]
>> [2, 9]
>> [10,13]
>> [11,12]
>>
>> I want to get the following merged intervals.
>>
>> [1,9]
>> [10,13]
>>
>> Could somebody let me know if there is a function in the python
>> library?

>
> No, but try this:
>
> def merge(intervals):
> if not intervals:
> return []
> intervals = sorted(intervals, key = lambda x: x[0])


Since Python uses lexical sorting and the intervals are lists isn't the
key specification redundant here?

> result = []
> (a, b) = intervals[0]
> for (x, y) in intervals[1:]:
> if x <= b:
> b = max(b, y)
> else:
> result.append((a, b))
> (a, b) = (x, y)
> result.append((a, b))
> return result
>

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
PyCon is coming! Atlanta, Feb 2010 http://us.pycon.org/
Holden Web LLC http://www.holdenweb.com/
UPCOMING EVENTS: http://holdenweb.eventbrite.com/

 
Reply With Quote
 
Jonathan Gardner
Guest
Posts: n/a
 
      02-11-2010
On Feb 10, 3:23*pm, Peng Yu <(E-Mail Removed)> wrote:
> I'm wondering there is already a function in python library that can
> merge intervals. For example, if I have the following intervals ('['
> and ']' means closed interval as inhttp://en.wikipedia.org/wiki/Interval_(mathematics)#Excluding_the_end...)
>
> [1, 3]
> [2, 9]
> [10,13]
> [11,12]
>
> I want to get the following merged intervals.
>
> [1,9]
> [10,13]
>
> Could somebody let me know if there is a function in the python
> library?


I vaguely recall a similar question a long time ago. Peng, is this a
homework assignment?

Perhaps we should add a standard module called "homework". It can have
functions for all the different homework assignments we see on
c.l.python. We can simply point people to this module and then can
include the code in their answers.
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      02-11-2010
* Jonathan Gardner:
> On Feb 10, 3:23 pm, Peng Yu <(E-Mail Removed)> wrote:
>> I'm wondering there is already a function in python library that can
>> merge intervals. For example, if I have the following intervals ('['
>> and ']' means closed interval as inhttp://en.wikipedia.org/wiki/Interval_(mathematics)#Excluding_the_end...)
>>
>> [1, 3]
>> [2, 9]
>> [10,13]
>> [11,12]
>>
>> I want to get the following merged intervals.
>>
>> [1,9]
>> [10,13]
>>
>> Could somebody let me know if there is a function in the python
>> library?

>
> I vaguely recall a similar question a long time ago. Peng, is this a
> homework assignment?
>
> Perhaps we should add a standard module called "homework". It can have
> functions for all the different homework assignments we see on
> c.l.python. We can simply point people to this module and then can
> include the code in their answers.


If it's possible, there was/is this guy over in clc.c++ who responded/responds
to homework questions with the most advanced, convoluted and, except for
misleading names, technically correct solutions.


Cheers,

- Alf
 
Reply With Quote
 
Peter
Guest
Posts: n/a
 
      02-11-2010
On Feb 12, 8:03*am, Jonathan Gardner <(E-Mail Removed)>
wrote:
> On Feb 10, 3:23*pm, Peng Yu <(E-Mail Removed)> wrote:
>
>
>
>
>
> > I'm wondering there is already a function in python library that can
> > merge intervals. For example, if I have the following intervals ('['
> > and ']' means closed interval as inhttp://en.wikipedia.org/wiki/Interval_(mathematics)#Excluding_the_end...)

>
> > [1, 3]
> > [2, 9]
> > [10,13]
> > [11,12]

>
> > I want to get the following merged intervals.

>
> > [1,9]
> > [10,13]

>
> > Could somebody let me know if there is a function in the python
> > library?

>
> I vaguely recall a similar question a long time ago. Peng, is this a
> homework assignment?
>
> Perhaps we should add a standard module called "homework". It can have
> functions for all the different homework assignments we see on
> c.l.python. We can simply point people to this module and then can
> include the code in their answers.


Good idea - that would (also) give the teachers a convenient place to
check for what assignments have been solved by this list so they can
propose something else.

They can also grade the submissions against the code kept in this area
- exact copies could receive an "F" (for example )

Peter
 
Reply With Quote
 
Nobody
Guest
Posts: n/a
 
      02-12-2010
On Wed, 10 Feb 2010 23:03:29 -0500, Steve Holden wrote:

>> intervals = sorted(intervals, key = lambda x: x[0])

>
> Since Python uses lexical sorting and the intervals are lists isn't the
> key specification redundant here?


Yes, but I wanted to make it explicit.

Well, omitting the key= would change the sorting order in the event that
multiple intervals have the same start, but it still won't affect the
result of the function overall.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is a merge interval function available? Peng Yu Perl Misc 3 02-14-2010 10:01 PM
every($key, $interval) function Ted Zlatanov Perl Misc 17 01-23-2008 07:15 PM
Interval/Time-lapse function on digital (foto)camera ellobo1968@gmail.com Digital Photography 14 08-05-2006 06:11 AM
Photoshop's "Merge to HDR" Function Annika1980 Digital Photography 11 12-18-2005 10:49 AM
Problems with PS CS2 Merge to HDR function? babalooixnay@hotmail.com Digital Photography 3 12-15-2005 02:43 AM



Advertisments