Name: Anonymous 2010-07-14 15:57
Hello /prog/,given a set of let's say 2000 integers 1,2,...,2000
and a 2000*2000 matrix A such that A(i,j) is either true or false, i need to find all the subsets J of cardinal 7 such that for all i,j in J, A(i,j) is true, and i need to do it very fast.
The best way i could find consists in generating a matrix 2000*2000 B such that B(i,j) is the list of all k such that A(i,k) and A(j,k) are true and k>j>i and an array C such that C(i) is the list of all k such that A(i,k) is true and k>i.
Then i just select a first element i1, then a second which is a member of C(i1), a third, member of B(i1,i2) and so on , calculating intersections of lists of B.
Unfortunately,this is not fast enough. I also thought about generating a 3D matrix D but it would require too much memory.
Any ideas ?
and a 2000*2000 matrix A such that A(i,j) is either true or false, i need to find all the subsets J of cardinal 7 such that for all i,j in J, A(i,j) is true, and i need to do it very fast.
The best way i could find consists in generating a matrix 2000*2000 B such that B(i,j) is the list of all k such that A(i,k) and A(j,k) are true and k>j>i and an array C such that C(i) is the list of all k such that A(i,k) is true and k>i.
Then i just select a first element i1, then a second which is a member of C(i1), a third, member of B(i1,i2) and so on , calculating intersections of lists of B.
Unfortunately,this is not fast enough. I also thought about generating a 3D matrix D but it would require too much memory.
Any ideas ?