Все возможные двоичные матрицы с некоторыми свойствами

Question

Мне нужно сгенерировать все возможные двоичные матрицы 4x4, которые имеют нули вдоль главной диагонали, являются симметричными и имеют шесть записей, равных 1. Некоторые примеры:

[[0,0,0,0],
 [0,0,1,1],
 [0,1,0,1],
 [0,1,1,0]],

[[0,1,1,0],
 [1,0,1,0],
 [1,1,0,0],
 [0,0,0,0]],  

[[0,1,0,1],
 [1,0,0,1],
 [0,0,0,0],
 [1,1,0,0]]

Как я могу сделать это в Python?

Answer 1

Это равносильно выбору трех из шести записей выше диагонали 1.

Из списка позиций выше диагонали в матрице 4 на 4:

sage: positions = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

используйте Sage's Subsets, чтобы получить все подмножества размера 3 из этих позиций.

sage: S = Subsets([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)], 3)

Затем построить соответствующие матрицы.

sage: [matrix(ZZ, 4, lambda i, j: (i, j) in s or (j, i) in s) for s in S]
[
[0 1 1 1]  [0 1 1 0]  [0 1 1 0]  [0 1 1 0]  [0 1 0 1]  [0 1 0 1]
[1 0 0 0]  [1 0 1 0]  [1 0 0 1]  [1 0 0 0]  [1 0 1 0]  [1 0 0 1]
[1 0 0 0]  [1 1 0 0]  [1 0 0 0]  [1 0 0 1]  [0 1 0 0]  [0 0 0 0]
[1 0 0 0], [0 0 0 0], [0 1 0 0], [0 0 1 0], [1 0 0 0], [1 1 0 0],

[0 1 0 1]  [0 1 0 0]  [0 1 0 0]  [0 1 0 0]  [0 0 1 1]  [0 0 1 1]
[1 0 0 0]  [1 0 1 1]  [1 0 1 0]  [1 0 0 1]  [0 0 1 0]  [0 0 0 1]
[0 0 0 1]  [0 1 0 0]  [0 1 0 1]  [0 0 0 1]  [1 1 0 0]  [1 0 0 0]
[1 0 1 0], [0 1 0 0], [0 0 1 0], [0 1 1 0], [1 0 0 0], [1 1 0 0],

[0 0 1 1]  [0 0 1 0]  [0 0 1 0]  [0 0 1 0]  [0 0 0 1]  [0 0 0 1]
[0 0 0 0]  [0 0 1 1]  [0 0 1 0]  [0 0 0 1]  [0 0 1 1]  [0 0 1 0]
[1 0 0 1]  [1 1 0 0]  [1 1 0 1]  [1 0 0 1]  [0 1 0 0]  [0 1 0 1]
[1 0 1 0], [0 1 0 0], [0 0 1 0], [0 1 1 0], [1 1 0 0], [1 0 1 0],

[0 0 0 1]  [0 0 0 0]
[0 0 0 1]  [0 0 1 1]
[0 0 0 1]  [0 1 0 1]
[1 1 1 0], [0 1 1 0]
]

Обратите внимание, что это матрицы смежности для всех графов с тремя ребрами на четырех помеченных вершинах.

Если вы хотите немаркированные вершины или эквивалентный список матриц смежности классов эквивалентности графов с тремя ребрами на четырех вершинах, вы можете использовать Nauty перечислять их. Вот как это сделать из Sage:

sage: G = graphs.nauty_geng("4 3:3")
sage: G
<generator object nauty_geng at 0x21c89a0f0>
sage: [g.adjacency_matrix() for g in G]
[
[0 0 0 1]  [0 0 1 1]  [0 0 1 1]
[0 0 0 1]  [0 0 0 1]  [0 0 0 0]
[0 0 0 1]  [1 0 0 0]  [1 0 0 1]
[1 1 1 0], [1 1 0 0], [1 0 1 0]
]