Симметричные матрицы 0,1

Question

Мне нужно создать все матрицы 0,1 NxN с нулевой диагональю. Матрицы должны быть симметричными. В каждом столбце и строке должно быть хотя бы одно 1. Любые идеи, которые могут помочь?

Answer 1

получать все возможные матрицы этой формы

Идея заключается в том, что каждая матрицу этого типа с размером NxN определяется его верхними диагональными значениями. Поэтому повторение всех возможных шаблонов для верхней диагональной части и совмещение этих значений с нижней диагональю сделают трюк. Пример кода:

%defines N 
N = 3; 

%calculates degree of freedom 
nValuesToRand = ((N*N) - N)/2; 

%generate all possible binary patterns of size nValuesToRand 
B = dec2bin(0:2^nValuesToRand - 1); 

%masks of lower and upper diagonal - will be used later on 
upperTriagonalMask = logical(triu(ones(N,N)) - eye(N)); 
lowerTriagonalMask = logical(tril(ones(N,N)) - eye(N)); 

%generates a new cell to hold the matrices 
allMatrices = cell(size(B,1),1); 

%iterates over all possible patterns 
for i=1:size(B,1) 

    %generates a new matrix 
    mat = zeros(N,N); 

    %initializes its upper diagonal according to the binary pattern 
    mat(upperTriagonalMask) = logical(B(i,:)- 48); 

    %copies the upper triagonal to the lower triagonal (for symmetricality) 
    upperTriagonalTransposed = triu(mat)'; 
    mat(lowerTriagonalMask) = upperTriagonalTransposed(lowerTriagonalMask); 

    %ignores illegal Matrices 
    if sum(sum(mat,2)==0)>0 
     continue; 
    end 

    %saves mat in the cell 
    allMatrices{i} = mat; 

end 

%cleanes cell 
allMatrices = allMatrices(~cellfun(@isempty, allMatrices)); 

Генерация случайных матриц

генерации всех возможных матриц для больших значений N вычислительно трудно. Если вы хотите создать матрицу случайным образом, вы можете попробовать следующий подход:

%Dimension size 
N = 6; 

%Probability for appearance of 0 
P = 0.5; 

%A mask of the lower diagonal, to be used later on 
lowerTriagonalMask = logical(tril(ones(N,N))); 

%initializes the matrix 
mat = zeros(N,N); 

%runs the loop as long as the matrix is not valid 
while (sum(mat,2)==0)>0 

    %defines a random binary matrix 
    mat = rand(N,N) > P; 

    %zero out the diagonal values 
    mat(logical(eye(N))) = 0; 

    %copies the upper triagonal to the lower triagonal (for symmetricality) 
    upperTriagonalTransposed = triu(mat)'; 
    mat(lowerTriagonalMask) = upperTriagonalTransposed(lowerTriagonalMask); 

end 

%testing 
issymmetric(double(mat)) 
mat 

результат:

ans = 

1 

mat = 

0  1  1  1  0  0 
1  0  1  1  1  1 
1  1  0  0  0  1 
1  1  0  0  0  1 
0  1  0  0  0  1 
0  1  1  1  1  0