Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2002
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2002

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

Search the Archive

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






  • Prev by Date: Re: grouping and averaging {x,y} pairs of data
  • Next by Date: Re: List processing
  • Previous by thread: RE: List processing
  • Next by thread: Re: List processing