Re: Find Upper Neighbor in a list
- To: mathgroup at smc.vnet.net
- Subject: [mg85062] Re: Find Upper Neighbor in a list
- From: sashap <pavlyk at gmail.com>
- Date: Sat, 26 Jan 2008 05:02:50 -0500 (EST)
- References: <fne2pm$5id$1@smc.vnet.net>
Hi Peter,
So the problem boils down to building a graph according to the partial
ordering by inclusion.
My approach is as follows:
In[24]:= el = {{5, 6}, {5, 6, 8}, {5, 6, 7, 8}, {1, 2, 3, 5, 6}, {1,
2, 3, 4, 5, 6, 7, 8}};
build all rules, where left set is subset of the right one.
In[42]:= e2 =
Cases[Rule @@@ Subsets[el, {2}],
HoldPattern[x_ -> y_] /; x === Intersection[x, y]]
Out[42]= {{5, 6} -> {5, 6, 8}, {5, 6} -> {5, 6, 7, 8}, {5, 6} -> {1,
2, 3, 5, 6}, {5, 6} -> {1, 2, 3, 4, 5, 6, 7, 8}, {5, 6, 8} -> {5,
6, 7, 8}, {5, 6, 8} -> {1, 2, 3, 4, 5, 6, 7, 8}, {5, 6, 7,
8} -> {1, 2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 5, 6} -> {1, 2, 3, 4, 5,
6, 7, 8}}
Now delete all the associations which are compositions of
In[46]:= graph =
FixedPoint[
Cases[#, HoldPattern[x_ -> y_] /;
Cases[el,
z_ /; MemberQ[#, Rule[z, y]] &&
MemberQ[#, Rule[x, z]], {1}] === {}, {1}] &, e2]
Out[46]= {{5, 6} -> {5, 6, 8}, {5, 6} -> {1, 2, 3, 5, 6}, {5, 6,
8} -> {5, 6, 7, 8}, {5, 6, 7, 8} -> {1, 2, 3, 4, 5, 6, 7, 8}, {1,
2, 3, 5, 6} -> {1, 2, 3, 4, 5, 6, 7, 8}}
this graph you can visualize using GraphPlot3D
In[47]:= GraphPlot3D[graph, VertexLabeling -> True]
Upper Neighbors are what follows {5,6} in this elementary
associations:
In[49]:= UpperNeighbours = ReplaceList[First[el], graph]
Out[49]= {{5, 6, 8}, {1, 2, 3, 5, 6}}
In essence this boils down to two loops, just in a functional
programming fashion.
Hope this helps.
Oleksandr Pavlyk
Wolfram Research
On Jan 25, 7:35 pm, P_ter <peter_van_summe... at yahoo.co.uk> wrote:
> Hello,
> I would like to find the Upper Neighbour of a set in a list, where the (lattice) order is inclusion. I have as example: {{3}, {4}, {6}, {7}, {2, 3}, {3, 4}, {3, 6}, {5, 6}, {6, 8}, {1, 2, 3}, {2, 3, 4}, {5, 6, 8}, {6, 7, 8}, {1, 2, 3, 4}, {5, 6, 7, 8}, {1,2, 3, 5, 6}, {3, 4, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8}}
> The subsets I call nodes. I form a list of lists where in each list the first member is a node which has an intersection with all the other nodes in the list.
> So a sublist is: {{5,6},{5,6,8},{5,6,7,8},{1,2,3,5,6},{1,2,3,4,5,6,7,8}}
> As one can see {5,6} is included in every other set in this list. The upper neigbor of {5,6} is {5,6,8} because there is no set in between. But also {1,2,3,5,6} is an upper neighbor, because there is no other set of the list in between it and (5,6}.
> I have this problem for a list of lists where the first member is the set for which the upper neighbour is sought.
> I solved it with loops, but I am not satisfied. Please, if someone has better ideas?
> Also, I have a second question. Once the upper neighbours are found, I want to plot it in GraphPlot3D (which is very convenient!). I convert every set with FromDigits and make a list of 56->568 etc. Better ideas are welcome.
> Thanks in advance,
> P_ter