Re: Unions
- To: mathgroup at yoda.physics.unc.edu
- Subject: Re: Unions
- From: TODD GAYLEY <TGAYLEY at ccit.arizona.edu>
- Date: Thu, 4 Jun 1992 06:28 MST
Zdravko Balorda (zdravc at robo.fer.yu) asks:
> Given n closed intervals find their Union. For instance:
> [0,2];[2,4];[1,5]
> The union of the above 3 intervals would be [0,5].
> The union of the following:
> [0,2];[3,5]
> would be [0,2][3,5].
Here's my solution. At first I wrote some ugly procedural code,
but I knew the WRI thought police would frown. I knew there
had to be a better way, a glorious one-liner, but my functional
programming skills failed me. But then, inspired by the "pattern-
based" answer to the recent Mma programming competition
(reported here by Richard Gaylord), I saw the light and came
up with the following (it's really a one-liner; the parentheses are
just to allow line breaks for readability). Hmm, maybe these
patterns aren't so "ugly" after all....
IntervalUnion[ intervalList_ ] := (
Sort[Sort /@ intervalList] //.
{a___, x_List, y_List, b___} /; y[[1]] < x[[2]]
:> {a, {x[[1]], Max[x[[2]], y[[2]]]}, b}
)
This function assumes that the input is a list of intervals that
are themselves in the form of lists, as in
{{1,2},{3,5},{-2,3}...}.
First, it sorts the list. The inner Sort allows the intervals to be
specified with either the high or low limit first. This sorting
step takes care of a lot of the work. Now, we only have to
check whether the low limit of the next interval is within the
bounds of the current interval. If it is, then expand the current
interval to the new upper limit. If not, then there will be a
discontinuity; do nothing. Basically, this implements the algorithm
suggested by Balorda. (Disclaimer: this function has been
throughly tested on at least two or three different inputs. Any bugs
are likely to be hardware problems in your computer. See your
vendor).
--Todd Gayley
--Department of Ecology and Evolutionary Biology
--University of Arizona