Умный способ генерации матрицы нулей и единиц в Matlab

Question

Я хотел бы сгенерировать все возможные матрицы смежности (нулевой диагональ) неориентированного графа n узлов.

Например, без переобозначения для n=3 мы получаем 2 ^{3 (3-1)/2 = 8} возможных конфигурации сети (или матрица смежности).

Одно решение, которое работает для n = 3 (и я думаю, это довольно глупо) будет следующим:

n = 3; 
A = []; 
for k = 0:1 
    for j = 0:1 
     for i = 0:1 
      m = [0 , i , j ; i , 0 , k ; j , k , 0 ]; 
      A = [A, m]; 
     end 
    end 
end 

Также я, хотя в следующем, который, кажется, быстрее, но что-то не так с моей индексации, так как 2 отсутствуют:

n = 3 
C = []; 
E = []; 

A = zeros(n); 

for i = 1:n 
    for j = i+1:n 
     A(i,j) = 1; 
     A(j,i) = 1; 
     C = [C,A]; 
    end 
end 

B = ones(n); 
B = B- diag(diag(ones(n))); 
for i = 1:n 
    for j = i+1:n 
     B(i,j) = 0; 
     B(j,i) = 0; 
     E = [E,B]; 
    end 
end 

D = [C,E] 

Есть ли более быстрый способ сделать это?

Answer 1

Я определенно генерировать недиагональными элементы матриц смежности с двоичным кодированием:

n = 4; %// number of nodes 
m = n*(n-1)/2; 
offdiags = dec2bin(0:2^m-1,m)-48; %//every 2^m-1 possible configurations 

Если у вас есть статистика и Machine Learning Toolbox, то squareform будет легко создать матрицы для вас, один за другим один:

%// this is basically a for loop 
tmpcell = arrayfun(@(k) squareform(offdiags(k,:)),1:size(offdiags,1),... 
       'uniformoutput',false); 
A = cat(2,tmpcell{:}); %// concatenate the matrices in tmpcell 

Хотя я бы рассмотреть конкатенации по измерению 3, то вы можете увидеть каждую матрицу индивидуально и удобно.

В качестве альтернативы, вы можете сделать массив синтез себя в векторизованном образе, это, вероятно, даже быстрее (за счет дополнительной памяти):

A = zeros(n,n,2^m); 
%// lazy person's indexing scheme: 
[ind_i,ind_j,ind_k] = meshgrid(1:n,1:n,1:2^m); 
A(ind_i>ind_j) = offdiags.'; %'// watch out for the transpose 

%// copy to upper diagonal: 
A = A + permute(A,[2 1 3]); %// n x n x 2^m matrix 

%// reshape to n*[] matrix if you wish 
A = reshape(A,n,[]);   %// n x (n*2^m) matrix