Thread Subject:

finding indentical neighbor elements

Sorry for the not-so-concise subject, I couldn't come up with one in less
than 10 words...

I have a vector that's some 400,000 elements long. Periodically in this
vector there are segments where there are "n" elements in a row that are
identical. Is there a "matlab-like" way to find where those segments
are? Ideally, I'd like the index of the first element and the last
element ("n" is variable within the vector) but would settle (beggars
can't be choosers :-) for either first or last. Also ideally, it should
handle NaN, +inf and -inf as well as finite numbers.

TIA,
Bruce

--
+-------------------+---------------------------------------------------+
Bruce Bowler | Experience is a good school, but the fees are high.
1.207.633.9600 | - Heine
bbowler@bigelow.org |
+-------------------+---------------------------------------------------+

Bruce Bowler <bbowler@bigelow.org> wrote in message <74hctpF13bmmpU1@mid.individual.net>...
> Sorry for the not-so-concise subject, I couldn't come up with one in less
> than 10 words...
>
> I have a vector that's some 400,000 elements long. Periodically in this
> vector there are segments where there are "n" elements in a row that are
> identical. Is there a "matlab-like" way to find where those segments
> are? Ideally, I'd like the index of the first element and the last
> element ("n" is variable within the vector) but would settle (beggars
> can't be choosers :-) for either first or last. Also ideally, it should
> handle NaN, +inf and -inf as well as finite numbers.
>
> TIA,
> Bruce
>
> --
> +-------------------+---------------------------------------------------+
> Bruce Bowler | Experience is a good school, but the fees are high.
> 1.207.633.9600 | - Heine
> bbowler@bigelow.org |
> +-------------------+---------------------------------------------------+

Bruce, the "unique" command should do what you want.

On Mon, 13 Apr 2009 18:08:01 +0000, Marco wrote:

> Bruce Bowler <bbowler@bigelow.org> wrote in message
> <74hctpF13bmmpU1@mid.individual.net>...
>> Sorry for the not-so-concise subject, I couldn't come up with one in
>> less than 10 words...
>>
>> I have a vector that's some 400,000 elements long. Periodically in
>> this vector there are segments where there are "n" elements in a row
>> that are identical. Is there a "matlab-like" way to find where those
>> segments are? Ideally, I'd like the index of the first element and the
>> last element ("n" is variable within the vector) but would settle
>> (beggars can't be choosers :-) for either first or last. Also ideally,
>> it should handle NaN, +inf and -inf as well as finite numbers.
>>
>> TIA,
>> Bruce
>>
>
> Bruce, the "unique" command should do what you want.

Maybe I'm missing something, but I don't see how unique (or any of it's
outputs) tells me there are 3 2s in a row in the following case

>> a=[8 2 2 2 7 4 4 8 9 1 2 3];
>> [b,i,j]=unique(a);
>> b
b =
     1 2 3 4 7 8 9
>> i
i =
    10 11 12 7 5 8 9
>> j
j =
     6 2 2 2 5 4 4 6 7 1 2 3



--
+-------------------+---------------------------------------------------+
Bruce Bowler | We learn from experience that men never learn
1.207.633.9600 | anything from experience. - Bernard Shaw
bbowler@bigelow.org |
+-------------------+---------------------------------------------------+

On Apr 13, 2:00=A0pm, Bruce Bowler <bbow...@bigelow.org> wrote:
> Sorry for the not-so-concise subject, I couldn't come up with one in less
> than 10 words...
>
> I have a vector that's some 400,000 elements long. =A0Periodically in thi=
s
> vector there are segments where there are "n" elements in a row that are
> identical. =A0Is there a "matlab-like" way to find where those segments
> are? =A0Ideally, I'd like the index of the first element and the last
> element ("n" is variable within the vector) but would settle (beggars
> can't be choosers :-) for either first or last. =A0Also ideally, it shoul=
d
> handle NaN, +inf and -inf as well as finite numbers.
>
> TIA,
> Bruce
>
> --
> +-------------------+---------------------------------------------------+
> Bruce Bowler =A0 =A0 =A0 =A0| Experience is a good school, but the fees a=
re high.
> 1.207.633.9600 =A0 =A0 =A0| - Heine =A0
> bbow...@bigelow.org |
> +-------------------+---------------------------------------------------+

---------------------------------------------------------------------------=
------
Use the diff() command. Look for where the difference is equal to
zero. That will be the (start+1) or middle of your runs. At each of
those starting points, scan for as long as the difference equals zero
to find your ending point of the run.

Bruce Bowler <bbowler@bigelow.org> wrote in message <74hctpF13bmmpU1@mid.individual.net>...
> Sorry for the not-so-concise subject, I couldn't come up with one in less
> than 10 words...
>
> I have a vector that's some 400,000 elements long. Periodically in this
> vector there are segments where there are "n" elements in a row that are
> identical. Is there a "matlab-like" way to find where those segments
> are? Ideally, I'd like the index of the first element and the last
> element ("n" is variable within the vector) but would settle (beggars
> can't be choosers :-) for either first or last. Also ideally, it should
> handle NaN, +inf and -inf as well as finite numbers.

I did one like this a while back, but it's Easter hols, so no ML at home and a pile of "stuff" tomorrow.

The basic tool here is sparse. Your vector can be cut into chunks with diff. Whenever diff is non-zero, increment your column number. Row numbers stay the same. Now you have a sparse matrix with each column representing a "run" if you've done the diff's right and have understood spare's calling convention. The rest is for you to finish. You could end up with a very pleasing one-liner.

Bruce Bowler <bbowler@bigelow.org> wrote in message <74hctpF13bmmpU1@mid.individual.net>...
> Sorry for the not-so-concise subject, I couldn't come up with one in less
> than 10 words...
>
> I have a vector that's some 400,000 elements long. Periodically in this
> vector there are segments where there are "n" elements in a row that are
> identical. Is there a "matlab-like" way to find where those segments
> are? Ideally, I'd like the index of the first element and the last
> element ("n" is variable within the vector) but would settle (beggars
> can't be choosers :-) for either first or last. Also ideally, it should
> handle NaN, +inf and -inf as well as finite numbers.

You could create a symmetric tridiagonal sparse matrix, where A(i,i+1) = 1 if x(i) == x(i+1), with a zero-free diagonal (A(k,k)=1 for all k). Then use dmperm to find the connected components of the graph. That would be one line of M. With the r output of dmperm, the block sizes are diff(r), and you can then use "find" to find all blocks of size n. Something like

n = length(x) ;
s = isequalwithequalnans (x(1:n-1),x(2:n)) ;
A = sparse (1:n-1,2:n, s, n, n) ;
A = A' + speye (n) ;
[p q r s] = dmperm (A) ;
find(diff(r) == n)

That gives you a list of all the blocks of size n.
If you want the first, use find(...,'first'), or the last with find(...,'last').

Bruce Bowler <bbowler@bigelow.org> wrote in message <74hctpF13bmmpU1@mid.individual.net>...
> I have a vector that's some 400,000 elements long. Periodically in this
> vector there are segments where there are "n" elements in a row that are
> identical. Is there a "matlab-like" way to find where those segments
> are? Ideally, I'd like the index of the first element and the last
> element ("n" is variable within the vector) but would settle (beggars
> can't be choosers :-) for either first or last. Also ideally, it should
> handle NaN, +inf and -inf as well as finite numbers.
>
> TIA,
> Bruce

  You say "'n' is variable within the vector" but you don't make it clear just how small n can be. Do you for example want the indices of just two successive equal elements? I will suppose here that for a given n you want the start and end indices of any succession of at least n elements. Let v be your given row vector.

 % Set n to desired value
 p = find([true,diff(v)~=0,true]);
 q = find(diff(p)>=n);
 x = [p(q);p(q+1)-1];

The first row of x will contain the first indices and the second row the last indices in v for sequences of at least n successively equal elements.

  This will work for inf and -inf values but I'm afraid all NaNs are considered by matlab unequal to everything else, including themselves. For seqences of NaNs to be considered equal you would need a somewhat more complex code.
  
Roger Stafford

Here is a trick to take care without much effort of Inf and NaN:

% Data
a=[1 1 1 inf inf 2 3 NaN NaN -inf -inf -inf NaN]

% Engine
[yum yam J]=unique(typecast(a,'uint64'));
first=find([true diff(J)~=0 true]);
l=diff(first);
% Results
first=first(1:end-1);
last=first+l-1;
asplit=mat2cell(a,1,l);

% Check
asplit{:}

% Bruno

Here is a trick to take care without much effort of Inf and NaN:

% Data
a=[1 1 1 inf inf 2 3 NaN NaN -inf -inf -inf NaN]

% Engine
[yum yam J]=unique(typecast(a,'uint64'));
first=find([true diff(J)~=0 true]);
l=diff(first);
% Results
first=first(1:end-1);
last=first+l-1;
asplit=mat2cell(a,1,l);

% Check
asplit{:}

% Bruno

On Tue, 14 Apr 2009 18:38:01 +0000, Roger Stafford wrote:

> Bruce Bowler <bbowler@bigelow.org> wrote in message
> <74hctpF13bmmpU1@mid.individual.net>...
>> I have a vector that's some 400,000 elements long. Periodically in
>> this vector there are segments where there are "n" elements in a row
>> that are identical. Is there a "matlab-like" way to find where those
>> segments are? Ideally, I'd like the index of the first element and the
>> last element ("n" is variable within the vector) but would settle
>> (beggars can't be choosers :-) for either first or last. Also ideally,
>> it should handle NaN, +inf and -inf as well as finite numbers.
>>
>> TIA,
>> Bruce
>
> You say "'n' is variable within the vector" but you don't make it
> clear just how small n can be. Do you for example want the indices of
> just two successive equal elements? I will suppose here that for a
> given n you want the start and end indices of any succession of at
> least n elements. Let v be your given row vector.
>
> % Set n to desired value
> p = find([true,diff(v)~=0,true]);
> q = find(diff(p)>=n);
> x = [p(q);p(q+1)-1];
>
> The first row of x will contain the first indices and the second row the
> last indices in v for sequences of at least n successively equal
> elements.
>
> This will work for inf and -inf values but I'm afraid all NaNs are
> considered by matlab unequal to everything else, including themselves.
> For seqences of NaNs to be considered equal you would need a somewhat
> more complex code.
>
> Roger Stafford

Roger,

Thanks. The above works perfectly (well, it didn't seem to work for +/-
inf, but...). As it turns out, closer inspection of the data reveals
there are some values that can *never* occur, so the first pass thru the
data is to set all values that aren't finite (nan, +/-inf) to one of
those values and then everything is "easy-breezy".

Bruce

--
+-------------------+---------------------------------------------------+
Bruce Bowler | The one-eyed man is king in the land of the blind -
1.207.633.9600 | Anonymous
bbowler@bigelow.org |
+-------------------+---------------------------------------------------+