Re: Re: aggregation of related elements in a list
- To: mathgroup at smc.vnet.net
- Subject: [mg61657] Re: [mg61611] Re: aggregation of related elements in a list
- From: leigh pascoe <leigh at cephb.fr>
- Date: Mon, 24 Oct 2005 21:07:16 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Dear Mathgroup,
I would like to construct a function to transform a list of integers
into a list of lists of related members. Suppose we have the finite list
{x1,x2,x3,..........xN}
and a test function ( relatedQ[x_,y_,n_] ) that decides whether two
elements are related. The actual test may vary, but returns True or
False for any two elements as a function of n (n is an independent
variable not the number of elements in the list}.
I would like to process this list to aggregate those members that are
related either directly to each other or to a common element. For
example if x1 is unrelated to any other element in the list, x2 is
related to x5 but not x7 and x5 is related to x7 etc. would produce the
list of lists
{{x1},{x2,x5,x7),.......}
To take a specific example, assume we have the list
list={1,2,6,7,8,9,11,16}
and that application of the relatedQ, test to all possible pairs yields
the list of related pairs
prlist={{1,2},{1,6},{2,6},{2,7},{6,7},{6,11},{7,8},{7,11},{11,16}}
Using the list and the list of related pairs we can deduce the desired
list of lists as
{{1,2,6,7,8,11,16},{9}}
Here's one suboptimal method. I give steps tailored for your example. It
shouldn't be too difficult encapsulate these steps into a nice function.
Here are the steps. Construct a transition matrix:
sp1 = SparseArray[Thread[prlist -> 1], {16, 16}];
sp2 = SparseArray[{#, #} -> 1 & /@ list, {16, 16}];
In[13]:=
t = sp1 + sp2 + Transpose[sp1]
Out[13]=
SparseArray[<24>, {16, 16}]
Multiply t by itself (and take it's sign) until the result doesn't change:
In[14]:=
FixedPoint[Sign[#.#]&,t]
Out[14]=
SparseArray[<50>, {16, 16}]
The different rows of the fixed point are the different sets you are
interested in:
In[15]:=
Union[Normal[%14]]
Out[15]=
{{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1}}
If you prefer a list of integer sets:
In[16]:=
Flatten[Position[#,1]]&/@%15
Out[16]=
{{}, {9}, {1, 2, 6, 7, 8, 11, 16}}
If 6 were not in the original list we would get instead
{{1,2},{7,8,11,16},{9}}
Since your original pair list had the pair {2,7}, I think the result should
still be {{1,2,7,8,11,16},{9}}. At any rate, to use the transition matrix
approach, you would need to delete all pairs that had elements not in your
list, and then look for the fixed point. In your example with 6 deleted from
list, you would also need to delete all 6s from prlist:
newprlist = DeleteCases[prlist,{6,_}|{_,6}]
and then proceed as before using newprlist instead of prlist. This method
does extra work based on how large your final integer sets are. However,
matrix multiplication of sparse matrices is extremely quick, so I think it
ought to be at least competitive with other approaches.
Carl Woll
Wolfram Research
Thanks to those who considered my problem.
Carl,
That works nicely after deleting the null set from the list at the end.
I have adapted the procedure to the more general context I want to use
it in. You are of course correct that deleting 6 from the original list
doesn't change the result (sorry about that).
I tried to follow the mathematics of the process underlying your code.
It seems that you set up indicator variables for the prlist elements
and also put indicators for the list elements on the diagonal. Then
succesive matrix products get larger, but the Sign of the matrix
converges to a steady state. Applying Sign to each element restores it
to a 0 or 1 indicator. The Sign of a matrix seems to be the sum of the
Sign function applied to each element in the matrix resulting from the
product, although I couldn't find this in the documentation.<br>
Why this process should converge is a bit unclear to me. Are there any
limiting cases where it might not work?