查找满足某些约束的无序行对的索引

Question

我在Matlab中有两个维度为9x1的向量U1和U2，它们都列出了从1到9的整数。

clear
U1=(1:1:9).';
U2=U1;

然后，我通过取U1和U2的笛卡尔乘积来构造大小为(9*9)x1的向量U

[ca, cb] = ndgrid(U1, U2);
U=[ca(:) cb(:)];

基本上，U的结构是

U=[1 1;
2 1;
...;
9 1;
---;
1 2;
...
9 2;
---;
...
9 9]

现在，我希望你能帮助构建一个向量ind，列出U的无序行对的行索引，这样：

(*(i~=k和j~=l，其中[i,j]、[k,l]是从U算起的两行

我写了一段代码，可以做我想做的事情，但由于下面的步骤1(，我觉得它不是很有效。你能帮助改进吗？

步骤1(从U中获取ALL无序行对的行索引

ind_temp=nchoosek([1:1:9^2], 2); %3240x2

步骤2(从ind_temp中删除不满足(*(的行索引

ind=cell(size(ind_temp,1),1);
for p=1:size(ind,1)
if U(ind_temp(p,1),1)~=U(ind_temp(p,2),1) && ...
U(ind_temp(p,1),2)~=U(ind_temp(p,2),2)
ind{p}=ind_temp(p,:);
end
end
ind=vertcat(ind{:});

Answer 1

这里没有必要使用for循环。或者，您可以计算U中所有行之间的hamming距离。hamming距离是不同坐标的百分比，因此如果行中的两个值都不匹配，则hamming距离将等于1。

d = squareform(pdist(U,'hamming')); % Hamming distance between all rows
d = triu(d); % Set all values below the diagonal to 0, so we don't get [1 2] and [2 1] in ind.
[q,w] = find(d==1); % q and w will be row/column of all d==1 values.
ind = [q w]; % Assemble ind
ind = sortrows(ind); % Only necessary to sort rows if you want results exactly matching your example

Answer 2

对代码进行矢量化是非常直接的(矢量化通常意味着删除循环(。例如，U(ind_temp(:,1),:)是具有从U获得的对的矩阵，但是根据ind_temp的第一列中的值来重复和排序。我们可以对第二列重复该操作，并直接比较所有对：

I = all(U(ind_temp(:,1),:) ~= U(ind_temp(:,2),:),2);

现在，I是具有与ind_temp(3240x1(相同长度的逻辑阵列，其指示对于ind_temp中的哪一对满足约束。我们可以使用此索引到ind_temp，如下所示：

ind = ind_temp(I,:);

在Octave上，这个矢量化代码比原始代码快了大约3个数量级。在MATLAB上，差异不会那么显著，但它仍然应该更快。