Re: Number of interval Intersections for a large number

*To*: mathgroup at smc.vnet.net*Subject*: [mg81727] Re: [mg81679] Number of interval Intersections for a large number*From*: Carl Woll <carlw at wolfram.com>*Date*: Tue, 2 Oct 2007 05:40:48 -0400 (EDT)*References*: <148249.53339.qm@web26014.mail.ukl.yahoo.com>

Peter van Summeren wrote: > Hello Carl, > in my first attempt the intervals are integers. In a second attempt > they will be real. Ok, here is one attempt: stacked[intervals_, tall_] := Module[{pts, ord, ends, pos}, pts = Flatten[intervals]; ord = Ordering[pts]; ends = Riffle[ConstantArray[1, Length[intervals]], ConstantArray[-1, Length[intervals]]][[ord]]; pos = Flatten@Position[Accumulate[ends], tall, 1]; {pts[[ord[[pos]]]], pts[[ord[[pos + 1]]]]} // Transpose ] Here is some random data: SeedRandom[1]; len = 1000; max = 1200; left = RandomReal[max, len]; right = Clip[left + RandomReal[max/100, len], {0, max}]; inputintervals = Transpose[{left, right}]; Here is a query for the intervals that are stacked 12 high: In[352]:= stacked[inputintervals, 12] // Timing Out[352]= {0., {{21.4082, 21.528}, {22.8809, 23.4344}, {23.5234, 23.8432}, {53.8756, 53.8975}, {384.889, 385.702}, {385.909, 386.037}, {386.733, 386.802}, {402.722, 402.889}, {403.136, 403.445}, {404.061, 404.353}, {404.626, 404.642}, {716.699, 716.814}, {716.896, 717.495}, {717.986, 718.264}, {718.383, 718.843}, {773.912, 774.066}, {775.314, 775.347}, {775.375, 776.492}, {776.529, 776.595}, {811.171, 811.284}, {811.761, 812.34}, {812.477, 812.494}, {812.761, 813.322}, {921.788, 921.887}, {921.957, 923.916}, {952.247, 952.261}}} As you can see, the time taken is 0, so hopefully this is fast enough for you :) Carl [snip] > > > ----- Original Message ---- > From: Carl Woll <carlw at wolfram.com> > To: Peter van Summeren <peter_van_summeren at yahoo.co.uk> > Sent: Monday, 1 October, 2007 6:02:01 PM > Subject: Re: [mg81679] Number of interval Intersections for a large > number of intervals > > Peter van Summeren wrote: > > > Hello Carl, > > thanks for mailing me, although you do not understand. > > I have a few thousand intervals {e1,e2,...} each of which is like > > {begin,end} > > The elements e are ordered according to their begin value. > > Some intervals do not intersect. But it also can be like this: > > <------> > > <-------------------> > > <------------------> > > So, in this case the first interval can be partioned : > > in a part which has no intersection with the other two, > > in a part which intersects twice, > > in a part which intersects three times, > > in a part which intersects two times. > > For each interval I make a Block[x] = > > UnitStep[x-beginvalue]-UnitStep[x-endvalue] > > I sum all the Blocks to one function and ask Reduce to find me a > > solution for those parts which intersects three times: > > Reduce[SumOfBlocks[x]==3,x] > > Because it is a sum of UnitSteps and where there are three times an > > intersection, the value is 3. > > And so on for 1,2,4,5,etc. > > I agree that using Reduce here will be slow. However, before attempting > to speed up the determination of the list of intervals of height 3, what > will you do with this list of intervals? Also, are the interval > endpoints integers or real numbers? > > Carl > > > It is a safe way to do it, but not so fast. Are there other > > algorithms? Where can I find them? > > I hope my questions are now clear. I am still learning to formulate my > > questions in a way that I can use functions in Mathematica which solve > > them. Sometimes the solutions from people take me to possibilities I > > never dreamed of. I relearn math. > > with friendly greetings, > > Peter > > > > ----- Original Message ---- > > From: Carl Woll <carlw at wolfram.com> > > To: P_ter <peter_van_summeren at yahoo.co.uk> > > Sent: Monday, 1 October, 2007 4:01:15 PM > > Subject: Re: [mg81679] Number of interval Intersections for a large > > number of intervals > > > > P_ter wrote: > > > > >Hello, > > >I have as example on the interval [0.0,12000.0] thousands of smaller > > intervals which overlap. I construct for each interval a UnitStep up > > and one down(a block). I order and sum them and I give it to Reduce > > with the question Reduce[SumOfAllBlocks[x]==<number>,x]. The result > > gives me the overlapping intervals which overlap <number>. From the > > result I take out the length of the overlaps and Tally them. It is > > safe, but slow. > > >Does anyone know something about this type of problems? With better > > algorithms? > > > > > > > > A bit of working code would go a long way towards helping me understand > > what you are trying to do. As it is, I can't figure out what you did, > > nor what you want to achieve. > > > > Carl > > > > > > ------------------------------------------------------------------------ > > Yahoo! Answers - Get better answers from someone who knows. Try it now > > > <http://uk.answers.yahoo.com/;_ylc=X3oDMTEydmViNG02BF9TAzIxMTQ3MTcxOTAEc2VjA21haWwEc2xrA3RhZ2xpbmU>. > > > ------------------------------------------------------------------------ > For ideas on reducing your carbon footprint visit Yahoo! For Good > <http://uk.promotions.yahoo.com/forgood/environment.html> this month.

**Re: Dependence of precision on execution speed of Inverse**

**Re: Modifying the Default stylesheet?**

**Re: Dependence of precision on execution speed of Inverse**

**Re: Re: Number of interval Intersections for a large number**