Re: a little nasty problem?
- To: mathgroup at smc.vnet.net
- Subject: [mg108791] Re: a little nasty problem?
- From: dh <dh at metrohm.com>
- Date: Wed, 31 Mar 2010 06:21:37 -0500 (EST)
- References: <hosi3h$o2h$1@smc.vnet.net>
Hi Francisco,
I am not sure if I understood correctly.
1) Create a chain by starting at the highest interval and take all
intervals that a lower than the preceding one.
2) delete the found intevalls with the exception of the highest one.
3) repeat until only the highest one remains
This can be done e.g. by:
int = {{"C", {0.5, 0.6}}, {"D", {0.1, 0.2}}, {"A", {0.8,
0.9}}, {"B", {0.4, 0.6}}, {"F", {0.6, 0.65}}, {"G", {0, 0.7}}};
alpha = int[[All, 1]];
low = int[[All, 2, 1]];(*lower indices*)
high = int[[All, 2, 2]];(*upper indices*)
ord = Reverse@Ordering[low];
res = {};
While[Length[ord] > 1,
AppendTo[res,
FoldList[If[high[[#1]] >= high[[#2]], #2, #1] &, First@ord, Rest@ord]
];
ord = Prepend[Complement[ord, Union[Flatten@res]], First[ord]];
];(*create chains*)
res = res /. {x1___, x_, x_, x2___} -> {x1, x,
x2};(*remove duplicates*)
Map[alpha[[#]] &, res, {2}](*replace numbers by characters*)
Daniel
On 30.03.2010 12:00, Francisco Gutierrez wrote:
> Dear Mathgroup:
> Suppose I have a series of intervals, and I create an order relation. E.g., x is a typical interval, x={0.6,0.9}, and x>=y if x[[1]]>=y[[1]] and x[[2]]>=y[[2]].
> If x[[1]]>=y[[1]] and x[[2]]<y[[2]], or viceversa, the intervals are incomparable.
> This relation violates [weakly] transitivity.
> Now, I have a set of intervals, and I want to create the lattice that this order relation generates (suppose the weak violation of transitivity does not pop up)..
> For example,int= {{C,{0.5,0.6}},{D,{0.1,0.2}},{A,{0.8,0.9}},{B,{0.4,0.6}},{F,{0.6,0.65}},{G,{0,0.7}}}
>
> I would like my code to put A at the top, with two chains: {A,F,C,B, D} and {A,G}. Of course, it ought to flag any antichain if it exists.
> Now, there are several ways to do this. But what I have been able to cook up is TERRIBLY inefficient. With 10 intervals it works no more. Is there an efficient code to make the job? I am trying to do something that is unfeasible?
>
> Perhaps I am naively attacking a problem that has no solution. Or perhaps I am naively suggesting an easy problem is solvable. Some help out there?
> Francisco
>
--
Daniel Huber
Metrohm Ltd.
Oberdorfstr. 68
CH-9100 Herisau
Tel. +41 71 353 8585, Fax +41 71 353 8907
E-Mail:<mailto:dh at metrohm.com>
Internet:<http://www.metrohm.com>