help-octave
[Top][All Lists]
Advanced

[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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]