MATLAB Central Newsreader - Identifying repeating pattern in a vector

Identifying repeating pattern in a vector

Eyal — Tue, 03 Nov 2009 13:50:13 -0500

Hi

I have a function running a loop where a value is added to a vector at
each iteration. So, for example, if the vector is x, it could look
like:

Iteration 1: x=[1]
Iteration 2: x=[1,3]
Iteration 3: x=[1,3,2]
Iteration 4: x=[1,3,2,6]
Iteration 5: x=[1,3,2,6,2]
Iteration 6: x=[1,3,2,6,2,6]
Iteration 7: x=[1,3,2,6,2,6,2]

and so on.

As can be seen in the example above, at some point a repeating pattern
of values may appear in x; this indicates the function has entered an
infinite loop. I would like to be able to catch the pattern, say for
example after 3 repeats. In the example above, that would be when the
last 6 values of x are [2,6,2,6,2,6]; however, I do not know the
values in advance, nor do I know the length of the repeating pattern
(e.g. it could be [2,4,6,3,2,4,6,3,2,4,6,3]), though for practical
purposes three values should be sufficient to catch this error.

Can anyone suggest a way to identify this repeating pattern?

Thx

Re: Identifying repeating pattern in a vector

Herve — Tue, 03 Nov 2009 14:47:02 -0500

n = size(x,2)

for a repeating pattern of size 3, then you could use a if function such as

if x(n) == x (n-3) && x(n-1) == x(n-4) && x(n-2) == x(n-5)

I guess that better matlab's users will find nicer solutions :)

Re: Identifying repeating pattern in a vector

Jos — Tue, 03 Nov 2009 15:11:02 -0500

Eyal <efleminge@gmail.com> wrote in message <e09c467a-b65f-4636-bb80-67ba02bff5da@d10g2000yqh.googlegroups.com>...
> Hi
>
> I have a function running a loop where a value is added to a vector at
> each iteration. So, for example, if the vector is x, it could look
> like:
>
> Iteration 1: x=[1]
> Iteration 2: x=[1,3]
> Iteration 3: x=[1,3,2]
> Iteration 4: x=[1,3,2,6]
> Iteration 5: x=[1,3,2,6,2]
> Iteration 6: x=[1,3,2,6,2,6]
> Iteration 7: x=[1,3,2,6,2,6,2]
>
> and so on.
>
> As can be seen in the example above, at some point a repeating pattern
> of values may appear in x; this indicates the function has entered an
> infinite loop. I would like to be able to catch the pattern, say for
> example after 3 repeats. In the example above, that would be when the
> last 6 values of x are [2,6,2,6,2,6]; however, I do not know the
> values in advance, nor do I know the length of the repeating pattern
> (e.g. it could be [2,4,6,3,2,4,6,3,2,4,6,3]), though for practical
> purposes three values should be sufficient to catch this error.
>
> Can anyone suggest a way to identify this repeating pattern?
>
> Thx

Why not compare the last N elements with the second-last N (if that is the right term for it?) elements? Something like

if isequal(X(end-N+1:end),X(end-N-N+1:end-N))
error('we are repeating ourselves ...') ;
end

hth
Jos

Re: Identifying repeating pattern in a vector

Matt — Tue, 03 Nov 2009 16:25:03 -0500

Eyal <efleminge@gmail.com> wrote in message <e09c467a-b65f-4636-bb80-67ba02bff5da@d10g2000yqh.googlegroups.com>...
> Hi
>
> I have a function running a loop where a value is added to a vector at
> each iteration. So, for example, if the vector is x, it could look
> like:
>
> Iteration 1: x=[1]
> Iteration 2: x=[1,3]
> Iteration 3: x=[1,3,2]
> Iteration 4: x=[1,3,2,6]
> Iteration 5: x=[1,3,2,6,2]
> Iteration 6: x=[1,3,2,6,2,6]
> Iteration 7: x=[1,3,2,6,2,6,2]
>
> and so on.
>
> As can be seen in the example above, at some point a repeating pattern
> of values may appear in x; this indicates the function has entered an
> infinite loop. I would like to be able to catch the pattern, say for
> example after 3 repeats. In the example above, that would be when the
> last 6 values of x are [2,6,2,6,2,6]; however, I do not know the
> values in advance, nor do I know the length of the repeating pattern
> (e.g. it could be [2,4,6,3,2,4,6,3,2,4,6,3]), though for practical
> purposes three values should be sufficient to catch this error.

It might be worthwhile explaining the process that generates x. It's obviously some kind of Markov process if 3 repititions is a certain indicator of an infinite loop. That means there might be a simpler state vector to monitor than the whole history of the process.