Re: unions ... Oops.
- To: mathgroup at yoda.physics.unc.edu
- Subject: Re: unions ... Oops.
- From: John Lee <lee at math.washington.edu>
- Date: Thu, 4 Jun 92 12:16:46 -0700
In response to a question from Zdravko Balorda, I posted a Mma function
that was supposed to compute the union of a set of intervals. However, as
David Jacobson pointed out to me, my solution fails for nested intervals.
Here's a slight modification that works correctly:
intervalunion2 [ listofintervals_ ] :=
Sort[listofintervals] //. {a___, {b_,c_}, {d_,e_}, f___} :>
{a, {b,Max[c,e]}, f} /; d <= c;
Someone else wrote to me asking about efficiency, and that got me thinking
that it would probably be more efficient to write a procedural solution
that makes exactly one pass across the sorted list of intervals. Here's a
version that does that: it's much uglier, but it seems to run about 7
times faster.
intervalunion4[ listofintervals_ ] := Module[{slist,newlist,i},
slist = Sort[listofintervals];
newlist = {slist[[1]]};
Do[
If[ newlist[[-1,2]] >= slist[[i,1]],
(*then*) newlist[[-1,2]] = Max[ newlist[[-1,2]], slist[[i,2]] ],
(*else*) AppendTo[newlist, slist[[i]] ] ],
{i,2,Length[slist]} ];
Return[ newlist ]
];
Jack Lee
Dept. of Mathematics
University of Washington
Seattle, WA