通过数组操作有效搜索包含子排列的排列？

一尘不染

通过数组操作有效搜索包含子排列的排列？

algorithm

我有一组整数，比如说S = {1，…，10}，还有两个矩阵N和M，它们的行是元素从S的顺序例如3和3的某些（但不一定是所有可能的）排列。分别为5，例如N
= [1 2 3; 2 5 3; …]，M = [1 2 3 4 5; 2 4 7 8 1; …]。

置换P的子置换Q只是P的索引子集，因此Q元素的索引顺序与P中其索引的顺序相同。示例：[2,4,7]为[2,3,4,6,7,1]的子置换，但[1,2,3]不是后者的子置换。

我需要一种有效的方法（例如，尽可能向量化和尽可能小的for循环）来查找

（1）来自M的所有置换具有来自N的子置换

和

（2）在M中从N找到每个子置换的次数。

到目前为止，我所拥有的是一个矢量化代码，该代码检查给定的单个子置换是否包含在M中（以及有多少次），但是然后我必须使用N的parfor循环，对于很大的Ns它将变慢。请注意，如果N不太大，则也可以通过简单地从给定的三元组构造可允许的5元组并将结果与M进行比较来解决该问题，但是如果N很快，它将比简单的强行执行慢很多足够大。

解决此问题的另一种方法如下：检查其行的N个模排列是否在一般意义上是M的子矩阵，即，是否有可能通过从M中删除元素来获得N行的排列。

抱歉，如果我的问题太基础了，我的背景是数学代数几何和表示论，我对MATLAB非常陌生。

编辑： 这是我的代码，用于检查M中单个k元组的存在：[代码]

function [A,f] = my_function(x,M)
%// returns all rows in M that contain x and the absolute frequency of x in M
%// suboptimal for checking combinations rather than permutations byy at least ~ 50%
k = size(x,2);
m = size(M,1);
R = zeros(m,k);
I = R;
Z = I;
    for j = 1:k   
        [R(:,j),I(:,j)] = max((M == x(j)),[],2); 
        Z(:,j) = R(:,j).*I(:,j);
    end
z = zeros(m,k-1);
    for j = 1:(k-1)
        z(:,j) = (Z(:,j) > 0 & Z(:,j) < Z(:,j+1)); 
    end
[v,~] = find(sum(z,2) == k-1);    
A = M(v,:);
f = length(v);
end

使用此功能，通过N进行检查只是（par）for循环的简单问题，我希望避免这种情况，而希望使用更快的矢量化解决方案。

阅读 228

2020-07-28

共1个答案

一尘不染

方法1

[val,ind] = max(bsxfun(@eq,permute(M,[4 2 1 3]),permute(N,[2 3 4 1])),[],2)
matches = squeeze(all(diff(ind,1)>0,1).*all(val,1))
out1 = any(matches,2) %// Solution - 1
out2 = sum(matches,1) %// Solution - 2

方法＃2

另一种避免permuting N并且可能更长寿的方法N-

[val,ind] = max(bsxfun(@eq,N,permute(M,[3 4 1 2])),[],4)
matches = squeeze(all(diff(ind,[],2)>0,2).*all(val,2))
out1 = any(matches,1) %// Solution - 1
out2 = sum(matches,2) %// Solution - 2

方法＃3

适用于大数据量的内存分配方法-

out1 = false(size(M,1),1);  %// Storage for Solution - 1
out2 = zeros(size(N,1),1);  %// Storage for Solution - 2
for k=1:size(N,1)
    [val3,ind3] = max(bsxfun(@eq,N(k,:),permute(M,[1 3 2])),[],3);
    matches = all(diff(ind3,[],2)>0,2).*all(val3,2);
    out1 = or(out1,matches);
    out2(k) = sum(matches);
end

方法＃4

适用于GPU的内存分配方法-

gM = gpuArray(M);
gN = gpuArray(N);

gout1 = false(size(gM,1),1,'gpuArray');  %// GPU Storage for Solution - 1
gout2 = zeros(size(gN,1),1,'gpuArray');  %// GPU Storage for Solution - 2
for k=1:size(gN,1)
    [val3,ind3] = max(bsxfun(@eq,gN(k,:),permute(gM,[1 3 2])),[],3);
    matches = all(diff(ind3,[],2)>0,2).*all(val3,2);
    gout1 = or(gout1,matches);
    gout2(k) = sum(matches);
end
out1 = gather(gout1);  %// Solution - 1
out2 = gather(gout2);  %// Solution - 2

现在，这种GPU方法已经吹走了所有其他方法。它使用M : 320000X5和N : 2100X3（与您的输入大小相同）运行，并用随机整数填充。使用GTX 750 Ti，只需花13.867873 seconds!!
因此，如果您的GPU具有足够的内存，这可能也是您的制胜法宝。

方法5

适用于GPU的极端存储方式

gM = gpuArray(M);
gN = gpuArray(N);

gout1 = false(size(gM,1),1,'gpuArray');  %// GPU Storage for Solution - 1
gout2 = zeros(size(gN,1),1,'gpuArray');  %// GPU Storage for Solution - 2
for k=1:size(gN,1)
    [val2,ind2] = max(bsxfun(@eq,gM,permute(gN(k,:),[1 3 2])),[],2);
    matches = all(diff(ind2,[],3)>0,3).*all(val2,3);
    gout1 = or(gout1,matches);
    gout2(k) = sum(matches);
end
out1 = gather(gout1);  %// Solution - 1
out2 = gather(gout2);  %// Solution - 2

2020-07-28