MathGroup Archive 1992

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: unions ... Oops.

  • To: mathgroup at
  • Subject: Re: unions ... Oops.
  • From: John Lee <lee at>
  • 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]]};
             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

  • Prev by Date: Solving eigenvalue problems for ode's
  • Next by Date: Re: Keeping 'f[x,y,z]' in derivative expressions
  • Previous by thread: Solving eigenvalue problems for ode's
  • Next by thread: Re: Keeping 'f[x,y,z]' in derivative expressions