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