Binary matrix with columns sums equal to an array numbers, with unique rows sums

Question

I have this input array:

[5, 3, 2, 4, 1, 3, 4]

and want to build binary matrices where sums of each column equal to the coresponding input array elements.

The matrix is of size 7 x 5.
The sums of rows create an array of numbers (of size 5 in this case). So I need to generate different combinations of columns so that the arrays of rows sums are uninque.

The initial matrix is this:

$$ \begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{matrix} $$

And the rows sums arrays will be

[7, 6, 5, 3, 1]

I understand that I could create all possible permutations for each column and then take only the unique rows sums arrays (like [7, 6, 4, 3, 2], [6, 6, 5, 3, 2]).

But could someone give an advice on how could it be optimized, or if there's an algorithm for this?

Thanks.

Answer 1

Perform permutations only on unique column sum values. In the case of [5,3,2,4,1,3,4], you would want to perform permutations on the columns which are in bold: [5,3,2,4,1,3,4], and keep the last 2 columns fixed in all your permutations.

Next, take the set of complementary columns: The columns where your column sum values add up to the total number of rows. In this case, column sum values [3,2] and [4,1] are complementary. While performing permutations for those columns, you would want to avoid multiple occurrences of rows sum matrix having all values 1.

For example if all permutations of [3,2] are performed, there would be 5C2 occurrence of row sum matrix = [1,1,1,1,1] corresponding to only those 2 columns.

So, if you avoid that particular duplicate, I guess this method should work.