Functional solution to union of intervals
- To: Mathematica user's group <MathGroup at yoda.physics.unc.edu>
- Subject: Functional solution to union of intervals
- From: Robby Villegas <Villegas at knox.bitnet>
- Date: Thursday, June 4 1992
Hello,
About the pattern-matching solution to the union-of-intervals problem: a
beautiful one-liner! Yet again, I'm highly impressed with the clever
applications patterns can be put to in Mathematica. It's always fun to do
things in a slew of different ways in Mathematica, though (as somebody
remarked in the past, this is one of the characteristics of the language that
makes it interesting), so here's an alternative method which, albeit not as
beautiful, is still a very Mathematica way of doing things, at least in some
aspects:
unite[{maximals___, {a_, b_}}, {x_, y_}] := {maximals, {a, Max[b, y]}} /;
N[a <= x <= b]
unite[{maximals___, {a_, b_}}, {x_, y_}] := {maximals, {a, b}, {x, y}}
unionComponents = Fold[unite, { First[sortedList] }, Rest[sortedList] ];
Preliminaries: With 'intervals' containing the original, unsorted list of
intervals, 'sortedList' has been assigned 'Sort[intervals]'. Or if you want
to allow the endpoints of an interval to be given as {right, left}, as someone
suggested in another posting, then
sortedList = Map[Sort, intervals, {0, 1}]
will sort both the individual intervals and the list of them (and in the right
order, since Map with a level-specification hits deeper levels before
shallower ones. We want sorting by left endpoint for this 'unite' function).
The scheme of the "program" is to build up a list of maximal intervals by
moving from right to left through the sorted list of ordered pairs, coalescing
intervals that have any overlap. At each step, it will compare the current
interval to the last interval in the list it is accumulating, and if they
overlap it will unite them and replace the last interval in the accumulating
list with this union. If they don't overlap, then the current interval is
guaranteed to be disjoint from it and all the previous ones, so the current
one is pushed on to the end of the accumulating list.
I can't do timing comparisons right now, but someone mentioned that doing
a single scan through the list would make the algorithm faster, and this
proceeds from beginning to end on the sorted list of intervals, so it might be
reasonably quick. I intend to try, when I get a chance, a single definition
for 'unite' using a conditional like 'If[ N[a <= x <= b], ...]', and/or using a
pure function (which seemed at first glance to require more complicated
references to sub-parts) like 'Function[{accumList, next}, <formula>]', but I
suspect they will not be faster, and perhaps slower. Others can attack the
efficiency of the codes, meanwhile. I tested this on a few lists generated by
commands like
intervals = Table[ Random[Integer, {-100, 100}] +
RandomVector[2, Integer, {-4, 4}], {100} ];
which created sets of intervals with a decent number of chains of overlapping
intervals, and with results suitable for the old visual union operation so I
could verify easily. So far, it seems to work. By the way, the function
RandomVector[n, type, range] simply calls Table[Random[type, range], {n}], so
it gives an n-vector of random numbers.
Just another application to reaffirm my love for Fold, the trusty slick
way to avoid loops and procedures! Not to mention FoldList, great for
debugging the first few, faulty functions you choose to Fold... :-)
Robby Villegas
Knox College
(Villegas at Knox.Bitnet)