CODEWITHSUNDEEP
arraysalgorithmmatlabsequences
user23709
user23709

Reputation: 161

Frequency of non-increasing and non-decreasing subsequences

Having a sequence of numbers of length L, I need to count how many non-decreasing and non-increasing sub-sequences of exact length are there. For example, if I have a sequence of length 15

2, 4, 11, 13, 3, 5, 5, 6, 3, 3, 2, 4, 2, 14, 15

I see that non-increasing sub-sequences are

13, 3

6, 3, 3 , 2

4, 2

and non-decreasing sub-sequences are

2, 4, 11, 13

3, 5, 5, 6

2, 4

2, 14, 15

So here I have

Since the maximum length of a non-decreasing (or non-increasing) sub-sequence can be 15 in this case, I thought about representing frequencies through vectors x for non-increasing and y for non-decreasing sub-sequences:

x = (0,2,0,1,0,0,0,0,0,0,0,0,0,0,0)

y = (0,1,1,2,0,0,0,0,0,0,0,0,0,0,0)

Expanding this to general case of sequence of length L, I wanted to go through the sequence and, using loops, count frequencies of subsequences of the exact lengths. How would I do that? I would create zero-vectors of length L and I would add 1 to the l-th element of zero matrix every time I meet a sub-sequence of length l.

Since my sequence will be of length of few thousands, I wouldn't ask Matlab to write them, but I would ask it to write me particular frequency.

Is this a good approach? Is there some function in Matlab that is doing this?

Upvotes: 3

Views: 626

Answers (2)

Robert Seifert
Robert Seifert

Reputation: 25232

How about that lovely one-line solution?

%// vector
A = [2, 4, 11, 13, 3, 5, 5, 6, 3, 3, 2, 4, 2, 14, 15]
%// number of digits in output
nout = 15;

seqFreq = @(vec,x) histc(accumarray(cumsum(~(-x*sign([x*1; diff(vec(:))]) + 1 )), ...
                   vec(:),[],@(x) numel(x)*~all(x == x(1)) ),1:nout).' %'

%// non-increasing sequences -> input +1
x = seqFreq(A,+1)
%// non-decreasing sequences -> input -1
y = seqFreq(A,-1)

x = 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 

y = 0 1 1 2 0 0 0 0 0 0 0 0 0 0 0

Explanation

%// example for non-increasing
q = +1;
%// detect sequences: value = -1
seq = sign([q*1; diff(A(:))]);
%// find subs for accumarray
subs = cumsum(~(-q*seq + 1));
%// count number of elements and check if elements are equal, if not, set count to zero
counts = accumarray(subs,A(:),[],@(p) numel(p)*~all(p == p(1)) );
%// count number of sequences
x = histc(counts,1:nout);

Upvotes: 2

Luis Mendo
Luis Mendo

Reputation: 112669

For non-decreasing sequences:

x = [2, 4, 11,13,3,5,5,6,3,3,2,4,2,14,15]; %// data
y = [inf x -inf]; %// terminate data properly
starts = find(diff(y(1:end-1))<0 & diff(y(2:end))>=0);
ends = find(diff(y(1:end-1))>=0 & diff(y(2:end))<0);
result = histc(ends-starts+1, 1:numel(x));

For non-increasing sequences, just change inequalities and sign of infs:

y = [-inf x inf]; %// terminate data properly
starts = find(diff(y(1:end-1))>0 & diff(y(2:end))<=0);
ends = find(diff(y(1:end-1))<=0 & diff(y(2:end))>0);
result = histc(ends-starts+1, 1:numel(x));

Upvotes: 1

Related Questions