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.
I have to say I really don't understand your problem. You have 2000x2000 entries in some format---who cares what---and you need to find which entries are true? There's no way other than checking each entry, unless you know there is some class of functions which generated the entries, in which case you might hope to discover it by only checking a few. But you're only checking 4,000,000 entries. Is this really that slow? Just slapping the integers from 0 to 3999999 into a list and filtering that for evenness took 1 second on my laptop in a toy language.
The best way i could find consists in generating a matrix 2000*2000 B
Talk about doubling your work.
Name:
Anonymous2010-07-14 16:16
I don't need to find which entries are true, all need to find all possible (i1,i2,i3,i4,i5,i6,i7)
such that A(i1,i2)=rue,A(i2,i3)=true .. etc (all 7*6/2 possibilities)
The most stupid way would take 2000^7 operations
To clarify, when you say for all i,j in J, A(i,j) is true
You mean given S ∈ J, and a, b ∈ S; A(a, b) = true? There are not 7*6/2 possibilities in this case, its 7P2 i.e.: 7 * 6. Are you implying that the matrix M is symmetric?
>>9
I don't see how searching for paths will help him find c*****s.
>>1
I think maybe you should reread your problem statement.
Name:
Anonymous2010-07-14 18:53
I will not be the first admitting that I understand your playing field, so to speak, but don't understand your goal. I believe, and this is just my belief, you want to, for any given i and any given j, test the boolean status of all matrix cells A such that A(i, j) to A(i, 2000) and A(i, j) to A(2000, j) is true and create smaller subsets of this field based on that information, taking more information as you go? Am I even halfway to your idea?
>>28
High praise indeed, but I'll have to disagree. He could have obfuscated it more, e.g. by starting with a short homework-like text suggesting a problem not usually associated with the clique problem. Additionally he could have withheld critical details until pressed for them.