a little nasty problem?
- To: mathgroup at smc.vnet.net
- Subject: [mg108746] a little nasty problem?
- From: Francisco Gutierrez <fgutiers2002 at yahoo.com>
- Date: Tue, 30 Mar 2010 05:00:27 -0500 (EST)
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