Most efficient algorithm in Python to generate all 6x6 (0,1) matrices with sum in columns and rows lower than 2?

Question

I am working on a problem which requires me to find all 6x6 (0,1) matrices with some given properties:

The sum of a row/column must be lower than 2.
The matrices are not symmetrical.

I am using this code:

import numpy as np
import itertools as it

n=6
li=[]

for i in it.product([0, 1], repeat = n**2):

  if (np.reshape(np.array(i), (n, n)).sum(axis=1)  < 2).all() and (np.reshape(np.array(i), (n, n)).sum(axis=0)< 2).all() :
    if (np.transpose(np.reshape(np.array(i), (n, n))) != np.reshape(np.array(i), (n, n))).any():

      li.append(np.reshape(np.array(i), (n, n)))

The problem is that this method has to go through all 68719476736 (0,1) matrices. After this piece of code I still have to impose extra conditions.

Is there a faster algorithm to find this list of matrices?

Edit: The problem I am working on is one to find unique adjacency matrices (graph theory) up to a certain equivalence class. For instance, in the 4x4 version of the problem I wanted to find all (0,1) matrices such that:

The sum in a row/column is lower than 2;
Are not symmetrical, i.e. A^T != A;
Also A^T != P^T A P, where P is a matrix representation of the dihedral group D8 (order 8) which is a subgroup of S4.

After this last step I get a certain number of matrices. If A relates to B through the relation B = P^T A P, then it represents the same matrix. I follow to choose only one representative of this equivalence class.

In the 4x4 problem I go from 65536 to 3.

My estimate of the result after sorting through the first condition (sums) is 46080. In the 6x6 problem, the group of transformations P is of order 48.

I don't have time to work this out, but I suspect starting with a valid matrix and finding permutations of it may be significantly faster. — user2699
Maybe you can take some tips from this somewhat similar question: stackoverflow.com/questions/47019047/… — m69 ''snarky and unwelcoming''
Could you explain some of the details a little more? The title says less than 2, the question says less than or equal to two. What symmetries are to be avoided? And maybe explain the extra conditions you'll be imposing later on; it may be useful to incorporate them into this step of the algorithm. — m69 ''snarky and unwelcoming''
@m69's link just obviated most of the answer I was posting. Nice work! Once you have a "saturated" matrix (every row & col sums to 2), you get the other solutions by flipping '1' entries. I recommend using some dynamic programming to avoid duplicating effort on unsaturated matrices. You still need a filter to avoid the symmetries you want to exclude. — Prune

lenik lenik · Accepted Answer · 2018-07-24T15:30:26

You have trouble with your math, because if the row/column sum is less than 2, it could be 0 or 1 -- that means that in every row/column can be only one non-zero elememt, which is 7^6 = 117649 possible matrices.

100k matrices is pretty much doable by using a brute force, with additional filtering to remove vertical/horizontal flips and diagonal symmetries.

Here's a simple code that should get you started:

import numpy as np
from itertools import permutations

for perm in permutations( range(7), 6 ) :  # there are only 5040 permutations
    m = np.zeros(6, 6)        # start with an empty matrix
    for i, j in enumerate(perm) :
        if j == 6 : continue  # all zeros
        m[i][j] = 1           # put `1` in the current (i)-th row, (j) pos

        # here you check `m` for symmetry and save it somewhere or not

Most efficient algorithm in Python to generate all 6x6 (0,1) matrices with sum in columns and rows lower than 2?

1 Answers