[SciPy-user] Combinatoric/Statistics: length of longest sequence
Dr. Hans Georg Krauthaeuser
hgk at et.uni-magdeburg.de
Sun Oct 29 07:32:23 CST 2006
I have a 2d-array A of p-values (coming from pairwise statistical tests
of N datasets). N is typically in the range of 100-1000. Now, given a
certain threshold, I want to find the longest subset S of range(N), so
that A[i][j]>threshold for all i,j from S.
Unfortunately, the array A is not 'sparse', i.e. a lot of pairs (i,j)
will fulfill A[i][j]>threshold (typically ~50% of the elements).
All I can think of are brute force algorithms that probably will run
forever because of the large number of possible combinations to check.
It would be great if someone could give a pointer to a smart algorithm.
If it is not possible to give the exact answer, what algorithm could be
used to get a good approximative answer?
More information about the SciPy-user