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