Re: List processing
- To: mathgroup at smc.vnet.net
- Subject: [mg37224] Re: List processing
- From: "Allan Hayes" <hay at haystack.demon.co.uk>
- Date: Thu, 17 Oct 2002 00:08:58 -0400 (EDT)
- References: <aokbp7$afv$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
"John Leary" <leary at paradise.net.nz> wrote in message news:aokbp7$afv$1 at smc.vnet.net... ............. > A list contains pairs of values, with each pair representing the lower and > upper edge of a sub-range. Some of the sub-ranges partially overlap, some > fully overlap, others don't overlap at all. The problem is to produce a > second list that contains the overall upper and lower edges of the > overlapping sub-ranges. > > A simple example : {{100,200},{150,250},{120,270},{300,400}} would result > in {{100,270},{300,400}}. John, Generate a list of pairs: lst=Table[{#,#+Random[Integer,{0,9}]}&[Random[Integer,{0,1000}]],{1000}]; A slow solution Sort[lst]//. {x___,{a_,b_},{c_,d_},y___}/;c<=b:>{x,{a,Max[b,d]},y}//Timing {5. Second,{{0,219},{221,431},{432,568},{569,599},{600,697},{699,1005}}} A faster one FixedPoint[{Min[#],Max[#]}&/@Split[Sort[#], #1[[2]]>=#2[[1]]&]&, lst]//Timing {0.22 Second,{{0,219},{221,431},{432,568},{569,599},{600,697},{699,1005}}} -- Allan --------------------- Allan Hayes Mathematica Training and Consulting Leicester UK www.haystack.demon.co.uk hay at haystack.demon.co.uk Voice: +44 (0)116 271 4198 Fax: +44 (0)870 164 0565