在 MATLAB 中从多个向量中找到递增的数字序列

Question

假设我们有三个向量，比如 a、b 和 c，包括递增的实数值，如下所示：

a=[3 4 19 22];    
b=[1 10 15];
c=[3 5 11];

什么是最有效的方法（不使用循环）在 MATLAB 中找到递增数字序列？

对于上面的例子，输出应该是这样的：

[3 10 11]
[4 10 11]

它们的第一个元素都来自 a，第二个元素来自 b，第三个元素来自 c，所以它们应该有三个递增的元素。注意：第一个数字必须来自a，第二个来自b，第三个来自c。

对于这个问题，使用循环不是一个好的选择，因为向量可能有更多的长度，并且在一般情况下向量的数量会增加，所以运行时间会很长。

如有任何帮助，我们将不胜感激…… 提前致谢

Answer 1

有几种方法可以解决这个问题，并且应该始终考虑时间与 space 收益。

方法 1（需要很多 space（n^3，其中 n 是数组的长度）但没有直接循环！）：

[A,B,C] = meshgrid(a,b,c);
idxs = find((A<B)&(B<C));
[ib,ia,ic] = ind2sub(size(A),idxs);
answer = [a(1,ia);b(1,ib);c(1,ic)];

方法 2（要求较少 space（n^2，其中 n 是数组的长度），但确实包含一个循环，但对于较大的 n 值似乎更快。这种方法是如果您只需要找到有多少个解决方案，速度会更快。):

ab = double(bsxfun(@lt,a',b));
bc = double(bsxfun(@lt,b',c));
abc = ab*bc;
numberOfAnswers = sum(abc(:));
[idx] = find(abc);
cumnum = [0;cumsum(abc(idx))];
[ia,ic] = ind2sub(size(abc),idx);
answer = zeros(3,numberOfAnswers);
for i = 1:numel(idx)
  answer(1,(cumnum(i)+1):cumnum(i+1)) = a(ia(i));
  answer(2,(cumnum(i)+1):cumnum(i+1)) = b((b>a(ia(i)))&(b<c(ic(i))));
  answer(3,(cumnum(i)+1):cumnum(i+1)) = c(ic(i));
end

编辑： 这两种方法都会给出一个 3-by-m-矩阵，其中 m 是解决方案的数量，并且解决方案将是矩阵的列。

在 MATLAB 中从多个向量中找到递增的数字序列

finding increasing sequences of numbres from several vectors in MATLAB

search

matlab

vector

vectorization

sequence