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?