Сохранять все возможные неориентированные графики

Question

Что такое эффективное решение для генерации всех возможных графиков с использованием матрицы инцидентов? Проблемы эквивалентны генерированию всей возможной бинарной треугольной матрицы. Моя первая идея заключалась в использовании python с itertools. Например, для создания всех матриц possibile 4x4

for b in itertools.combinations_with_replacement((0,1), n-3): 
    b_1=[i for i in b] 
    for c in itertools.combinations_with_replacement((0,1), n-2): 
     c_1=[i for i in c] 
     for d in itertools.combinations_with_replacement((0,1), n-1): 
      d_1=[i for i in d] 

, а затем создать матрицу, добавив соответствующее число нулей .. Но это не правильно, так как мы пропускаем некоторые графики ...

Так , есть идеи? Возможно, я могу использовать изоморфизм между R^n-матрицей и вектором R^(n * n) и создать весь возможный вектор из 0 и 1, а затем разрезать его на мою матрицу, но я думаю, что есть более эффективные решения.

Спасибо

добавить вкладку MatLab, потому что это проблема, которую вы можете иметь в численном анализе и MATLAB.

Answer 1

Вот пример решения с использованием numpy, который генерирует все простые графики: Сначала он генерирует индексы верхней треугольной части iu. Цикл преобразует число k в его двоичное представление, а затем присваивает его верхней треугольной части G[iu].

import numpy as np 

n = 4 
iu = np.triu_indices(n,1) # Start at first minor diagonal 
G = np.zeros([n,n]) 

def dec2bin(k, bitlength=0): 
    return [1 if digit=='1' else 0 for digit in bin(k)[2:].zfill(bitlength)] 

for k in range(0,2**(iu[0].size)): 
    G[iu] = dec2bin(k, iu[0].size) 
    print(G) 

Answer 2

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

n = 4; %// matrix size 
vals = dec2bin(0:2^(n*(n+1)/2)-1)-'0'; %// each row of `vals` codes a matrix 
mask = tril(reshape(1:n^2, n, n))>0; %// decoding mask 
for v = vals.' %'// `for` picks one column each time 
    matrix = zeros(n); %// initiallize to zeros 
    matrix(mask) = v; %// decode into matrix 
    disp(matrix) %// Do something with `matrix` 
end 

Каждая итерация дает одну возможную матрицу. Например, первые матрицы для n=4 являются

matrix = 
    0  0  0  0 
    0  0  0  0 
    0  0  0  0 
    0  0  0  0 

matrix = 
    0  0  0  0 
    0  0  0  0 
    0  0  0  0 
    0  0  0  1 

matrix = 
    0  0  0  0 
    0  0  0  0 
    0  0  0  0 
    0  0  1  0 

matrix = 
    0  0  0  0 
    0  0  0  0 
    0  0  0  0 
    0  0  1  1