MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: aggregation of related elements in a list

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


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


To take a specific example, assume we have the list


and that application of the relatedQ, test to all possible pairs yields
the list of related pairs


Using the list and the list of related pairs we can deduce the desired
list of lists as


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}];

t = sp1 + sp2 + Transpose[sp1]
SparseArray[<24>, {16, 16}]

Multiply t by itself (and take it's sign) until the result doesn't change:

SparseArray[<50>, {16, 16}]

The different rows of the fixed point are the different sets you are 
interested in:

{{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:

{{}, {9}, {1, 2, 6, 7, 8, 11, 16}}

    If 6 were not in the original list we would get instead


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. 


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.&nbsp; Are there any
limiting cases where it might not work?

  • Prev by Date: Re: JLink discover and link to an already running kernel from a Java App
  • Next by Date: Re: Re: Use of CAS in introductory science&engineering courses
  • Previous by thread: Re: Re: aggregation of related elements in a list
  • Next by thread: Re: aggregation of related elements in a list