[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Newbie - Common value patterns in many vectors
From: |
Francesco Potortì |
Subject: |
Re: Newbie - Common value patterns in many vectors |
Date: |
Wed, 05 Oct 2011 19:21:18 +0200 |
>>I have a large number of vectors. Each contains from 1 to 100 numbers,
>>and each number is within the range 1-60. I need to find the vectors
>>containing N common numbers. For example, here are 6 vectors:-
>>
>>1 12 28 46
>>12 16 46 49 52 58
>>8 12 24 28 33 45 46 47 53 57
>>9
>>12 16 24 28 46 52
>>18 33 45
>>
>>If N is 3, then I am looking for any vectors containing at least 3
>>common values.
>>
>>In this case, vectors 1,3,5 have "12 28 46" in common and vectors 2,5
>>have "12 16 46 52" in common.
>>
>>The final result would be 2 vectors - (1,3,5) and (2,5).
>>
>>I can have the vectors as an array but then I would need an array of
>>(thousands,100) where most of the array entries would be zero, since 90%
>>of the vectors/rows would have < 10 elements.
>>
>
>Yes, the numbers in each vector are all different - there are no duplicates
>within each vector.
The easiest and most probably fastest is , for N vectors, to create an
Nx100 matrix of logicals, like this:
A = false(N,100);
and then populate it with the numbers.
In your example, you would write:
A(1,[1 12 28 46]) = true;
A(2,[12 16 46 49 52 58]) = true;
A(3,[8 12 24 28 33 45 46 47 53 57]) = true;
A(4,[9]) = true;
A(5,[12 16 24 28 46 52]) = true;
A(6,[18 33 45]) = true;
Memory consumption is very small, around N*100 bytes.
Finding the number of common elements between vectors x and y amounts
to:
sum(A(x,:) & A(y,:))
or, between x, y and z:
sum(A(x,:) & A(y,:) & A(z,:))
This can be extended to any number of vectors.
As for the best algorithm for finding the sets you want, I have no idea
and I suspect that the problem is exponential with N.
--
Francesco Potortì (ricercatore) Voice: +39.050.315.3058 (op.2111)
ISTI - Area della ricerca CNR Mobile: +39.348.8283.107
via G. Moruzzi 1, I-56124 Pisa Fax: +39.050.315.2040
(entrance 20, 1st floor, room C71) Web: http://fly.isti.cnr.it