非递增和非递减子序列的频率

Question

给定一个长度为L的数字序列，需要计算出有多少个非递减和非递增的恰好具有指定长度的子序列。例如，如果我有一个长度为15的序列：

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

我可以看到非递增的子序列是：

13, 3 6, 3, 3, 2 4, 2

非递减的子序列是：

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

因此，在这里我有：

- 2个长度为2的非递增子序列 - 1个长度为4的非递增子序列 - 2个长度为2的非递减子序列 - 1个长度为3的非递减子序列 - 2个长度为4的非递减子序列

由于在这种情况下非递减（或非递减）子序列的最大长度可以达到15，因此我考虑通过向量x表示非递减的频率，而向量y表示非递增的频率。

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)

将这个问题扩展到长度为L的序列的一般情况，我想通过循环遍历序列，并计算确切长度的子序列的频率。如何做到这一点？我会创建长度为L的零向量，并在每次遇到长度为l的子序列时，在零矩阵的第l个元素上加1。

由于我的序列长度为数千个，我不会要求Matlab将它们都写出来，但我会要求它给我写出特定的频率。

这是一个好方法吗？ 在Matlab中是否有某个函数可以完成这个任务？

- user23709

---

当你将[3 3]视为非递减时，你也应该将[5 5]视为非递增。否则会变得很棘手。在两个答案中，x将是x = (0,3,0,1,0,0,0,0,0,0,0,0,0,0,0)。 - Robert Seifert

我犯了一个错误，感谢你指出来。3,3与6,3,3,2配对，5,5与3,5,5,6配对。实际上，我不能将3,3和5,5归类为非递减或非递增序列，因为它们是常数。我会在问题中进行更正。我将尝试这段代码，并告诉你它是否有效。谢谢！ - user23709

那么你应该称其为“递增”和“递减”，而不是“非递减”和“非递增”。 - Robert Seifert

我知道 :) 让a、b和c是三个任意的数字，使得a<b<c。 a、b、c是严格递增的序列。 c、b、a是严格递减的序列。 a、a、b、c是非递减的（它不会减少，但有一个a的重复）。 c、b、b、a是非增的（它不会增加，但有一个b的重复）。递增序列也是非递减的，递减序列也是非递增的。我正在寻找这样的序列。现在可以了吗？ - user23709

是的，我明白了，这就是我理解你的问题的方式。但是你说“我不能将3,3或5,5归类为非递减或非递增序列，因为它们是常数。”- 我不同意这一点。无论如何，如果你需要排除这些情况，我会看看如何编辑我的问题，但我现在没有时间。 - Robert Seifert

Answer 1

那个漂亮的一行代码解决方案如何？

%// 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 

说明

%// 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);

- Robert Seifert

Answer 2

对于非递减序列：

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));

对于非递增序列，只需改变不等式和inf符号：

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));

- Luis Mendo