«симметричное» обнаружение строк в Matlab

Question

У меня есть целочисленная матрица A (nA x c) с четным числом столбцов (например, mod(c,2) = 0) и уникальными строками. Как эффективно (с помощью функции оптимизации скорости и памяти symmetricRows) найти «симметричные» строки матрицы A, iA1 и iA2, где «симметричные c» строки iA1 и iA2 определяется как:

all(A(iA1,1:end/2) == A(iA2,end/2+1:end) & A(iA1,end/2+1:end) == A(iA2,1:end/2),2) = true

Пример ():

A = [1 1 1 1; 
     2 2 2 2; 
     1 2 3 4;
     4 3 2 1; 
     2 2 3 3; 
     3 4 1 2;  
     3 3 2 2]
[iA1, iA2] = symmetricRows(A)
iA1 =
        1
        2
        3
        5       
iA2 =
        1
        2
        6
        7

Типичный размер матриц A: nA ~ 1e4 to 1e6, c ~ 60 to 120

Проблема мотивирована путем предварительной обработки большого набора данных, где «симметричные» строки не имеют значения с точки определяемого пользователем расстояния metri c.

Пример 2: для подготовки большего набора тестовых данных можно использовать этот функция , а затем, например:

N = 10;    
A = allcomb([1:N],[1:N],[1:N],[1:N]);
iA = symmetricRows(A)

Answer 1

Если у вас есть набор инструментов статистики:

d = ~pdist2(A(:,1:end/2), A(:,end/2+1:end));
[iA1, iA2] = find(triu(d & d.'));

Answer 2

Вы можете сделать это с неявным расширением для создания трехмерной матрицы сравнений, если у вас достаточно памяти.

AL = A(:,1:end/2);
AR = A(:,end/2+1:end);
AcompLR = squeeze( all( AL == reshape( AR.', 1, 2, [] ), 2 ) ); 
AcompRL = squeeze( all( reshape( AL.', 1, 2, [] ) == AR, 2 ) ); 

[iA(:,1), iA(:,2)] = find( AcompLR & AcompRL );
iA = unique( sort(iA,2), 'rows' );

Возвращает iA, где столбец 1 - это ваш iA1, а столбец 2 - это ваш iA2.

Обратите внимание, что мне нужно было unique, чтобы избежать обратных совпадений, т. е. [5,7]/[7,5]

Я не делал никаких тестов, но это может быть быстрее, чем циклы все делается за одну операцию. Вместо этого мы могли бы быть умнее с индексированием и делать только необходимые сравнения, это сэкономило бы память и вызов unique:

% Create row indices to cover all combinations of rows
rIdx = arrayfun( @(x) [ones(x,1)*x,(1:x).'], 1:size(A,1), 'uni', 0 );
rIdx = vertcat( rIdx{:} );
% Logical indexing comparisons
iA = rIdx( all( A( rIdx(:,1), 1:end/2 ) == A( rIdx(:,2), end/2+1:end ), 2 ) & ...
           all( A( rIdx(:,2), 1:end/2 ) == A( rIdx(:,1), end/2+1:end ), 2 ), : );