Найти индексы неупорядоченных пар строк, удовлетворяющих некоторым ограничениям

Question

У меня есть два вектора U1 и U2 в Matlab измерения 9x1, в обоих перечисляются целые числа от 1 до 9.

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

Затем я строю вектор U размером (9*9)x1, взяв декартово произведение U1 и U2

[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) Возьмите индексы строк ALL неупорядоченных пар строк из U

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

Векторизовать этот код довольно просто (векторизация обычно означает удаление циклов).Например, 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 разница не будет столь существенной, но она все равно будет значительно быстрее.

Answer 2

Нет необходимости использовать цикл for здесь.В качестве альтернативы вы можете рассчитать расстояние Хэмминга между всеми строками в U.Расстояние Хэмминга - это процент различных координат, поэтому, если ни одно из двух значений в строке не совпадает, расстояние Хэмминга будет равно 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