RE: Interval arithmetic, of a sort
- To: mathgroup at smc.vnet.net
- Subject: [mg33776] RE: [mg33721] Interval arithmetic, of a sort
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Tue, 16 Apr 2002 03:50:24 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
> -----Original Message----- > From: DIAMOND Mark R. [mailto:dot at dot.dot] To: mathgroup at smc.vnet.net > Sent: Wednesday, April 10, 2002 6:49 AM > To: mathgroup at smc.vnet.net > Subject: [mg33776] [mg33721] Interval arithmetic, of a sort > > > I cannot find any solution to this problem without using very > time consuming > procedural programming, and yet it seems that it ought to > have a reasonably > simple functional solution. BTW: Even though I don't use it in the > following, I am familiar with the Interval notation and functions. > > The origin of the programming problem is most easily pictured > as one of > laying down numbered strips of cardboard on top of one > another within an > interval. For simplicity, assume that the total interval is > Interval[{0,100}], which I will just write as {0,100}, and it > has the value > 1, with the notation now being {1,{0,100}} > > Uniquely numbered strips of card are put on top of this one; > they may or may > not overlap; I want to be able to obtain a description of the > visible bits > of card at the end. So for example, if "+" indicates laying down a new > numbered strip, and if we start with > {{1,{0,100}}}, then {{{1,{0,100}}} + {2,{2,3}} = > {{1,{0,2}},{2,{2,3}},{1,{3,100}}, > indicating that the original strip is visible from 0-2, > strip 2 is visible > from 2-3, and the original is again visible from 3-100. > Continuing, complete > occlusion would happen with > {{1,{0,2}},{2,{2,3}},{1,{3,100}}, + {3,{1,20}} = > {{1,{0,1}},{3,{1,20}},{1,{20,100}}}; again continuing, > overlap would happen > with > {{1,{0,1}},{3,{1,20}},{1,{20,100}}} + {4,{15,30}} = > {{1,{0,1}},{3,{1,15}},{4,{15,30}},{1,{30,100}}} > > Mark R. Diamond > No spam email ROT13: znexq at cfl.hjn.rqh.nh > No crawler web page ROT13 uggc://jjj.cfl.hjn.rqh.nh/hfre/znexq > > > > Mark, here another solution. If you stack up high your intervals, it might be of advantage to locate the new overlayed Interval by binary search. To do that I'd propose a simplified data structure for your problem, which only marks the beginning of an interval; the end ist the just the beginning of the the next one. << DiscreteMath`Combinatorica` ?BinarySearch The overlaying function is: Attributes[overlay] = {HoldFirst} overlay[l_, {layer_, {start_, stop_}}] /; start <= stop := Module[{firstx = Floor[BinarySearch[l, start, Last]], lastx = Floor[BinarySearch[l, stop, Last]]}, l = Join[Take[l, firstx], {{layer, start}, {l[[lastx, 1]], stop}}, Drop[l, lastx]] ] We start with l = {{0, -Infinity}} {{0, -\[Infinity]}} "blank table", so to speak overlay[l, {1, {0, 100}}] {{0, -\[Infinity]}, {1, 0}, {0, 100}} overlay[l, {2, {2, 3}}] {{0, -\[Infinity]}, {1, 0}, {2, 2}, {1, 3}, {0, 100}} overlay[l, {3, {1, 20}}] {{0, -\[Infinity]}, {1, 0}, {3, 1}, {1, 20}, {0, 100}} overlay[l, {4, {15, 30}}] {{0, -\[Infinity]}, {1, 0}, {3, 1}, {4, 15}, {1, 30}, {0, 100}} Now you can revert to your notation with: (Transpose[{#1, Partition[#2, 2, 1, {1, 1}, Unevaluated[Infinity]]}] &) @@ Transpose[l] {{0, {-\[Infinity], 0}}, {1, {0, 1}}, {3, {1, 15}}, {4, {15, 30}}, {1, {30, 100}}, {0, {100, \[Infinity]}}} I you like, cut off the rests of the table-linen hanging down on both sides. FromCharacterCode[(If[97 <= # <= 122, Mod[# + 13, 26, 97], #] &) /@ ToCharacterCode["tbbq yhpx\n\n--\nHnegzhg"]]