algorithm - 向量化搜索包含给定子排列(带重复)的排列(带重复)

Question

这个问题可以看作是我之前的问题的延续/扩展/概括here .

一些定义:我有一组整数 S = {1,2,...,s} ，比如说s = 20 ，和两个矩阵 N和M其行是 S 中的有限数字序列(即可能重复的排列)，顺序为 n和m分别为 1 <= n <= m 。让我们想想N作为来自 M 的序列的候选子序列的集合。

示例:[2 3 4 3]是 [1 2 2 3 5 4 1 3] 的子序列多重性 2 时发生这种情况(=可以通过多少种不同的方式在主序列中找到子序列)，而 [3 2 2 3]不是它的子序列。特别是，根据定义，有效的子序列必须保留索引的顺序。

问题陈述:

(P1) 对于 M 的每一行，获取其在N中出现的有重数和无重数的子序列的数量作为行(如果 N 中不包含任何行，则可以为零)；

(P2) 对于 N 的每一行，找出 M 中包含多少次(有重数和无重数)作为子序列(同样，该数字可以为零)；

示例: 让 N = [1 2 2; 2 3 4]和M = [1 1 2 2 3; 1 2 2 3 4; 1 2 3 5 6] 。然后(P1)返回[2; 3; 0]对于“具有多重性”和 [1; 2; 0]对于“没有多重性”。 (P2) 返回 [3; 2]对于“具有多重性”和 [2; 1]没有多重性。

数量级: M通常最多可以有 30-40 列和几千行，尽管我目前有 M只有几百行和大约 10 列。 N可能接近的大小 M或者也可以小得多。

到目前为止我所拥有的:说实话，不多。我相信我也许能够稍微修改我之前的问题中不太好的向量化解决方案，以解决重复的排列，但我仍在考虑这一点，并且一旦我有工作，我就会更新。但鉴于我到目前为止(缺乏)经验，这很可能非常次优:(

谢谢!

Answer 1

简介:由于每行输入数据的重复性，组合查找过程在被利用的元素之间不具有“唯一性”类型在你之前的问题中，因此这里使用了循环。另外，请注意，without multiplicity 代码不使用 nchoosek，因此，我对它们的性能感到更加乐观。

符号:

p1wim -> P1 with multiplicity
p2wim -> P2 with multiplicity
p1wom -> P1 without multiplicity
p2wom -> P2 without multiplicity

代码:

我。具有多重性的 P1、2 的代码

permN = permute(N,[3 2 1]);

p1wim(size(M,1),1)=0;
p2wim(size(N,1),1)=0;

for k1 = 1:size(M,1)
    d1 = nchoosek(M(k1,:),3);
    t1 = all(bsxfun(@eq,d1,permN),2);
    p1wim(k1) = sum(t1(:));
    p2wim = p2wim + squeeze(sum(t1,1));
end

二. P1, 2 的代码，无重数

eqmat = bsxfun(@eq,M,permute(N,[3 4 2 1])); %// equality matrix

[m,n,p,q] = size(eqmat); %// get sizes
inds = zeros(size(M,1),p,q); %// pre-allocate for indices array

vec1 = [1:m]'; %//' setup constants to loop
vec2 = [0:q-1]*m*n*p;
vec3 = permute([0:p-1]*m*n,[1 3 2]);

for iter = 1:p
    [~,ind1] = max(eqmat(:,:,iter,:),[],2);
    inds(:,iter,:) = reshape(ind1,m,1,q);
    ind2 = squeeze(ind1);
    ind3 = bsxfun(@plus,vec1,(ind2-1)*m); %//' setup forward moving equalities
    ind4 = bsxfun(@plus,ind3,vec2);
    ind5 = bsxfun(@plus,ind4,vec3);
    eqmat(ind5(:)) = 0;
end

p1wom = sum(all(diff(inds,[],2)>0,2),3);
p2wom = squeeze(sum(all(diff(inds,[],2)>0,2),1));

像往常一样，我鼓励您也将 gpuArrays 与您最喜欢的 parfor 一起使用。