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

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.

• So you want to find all possible (distinct) arrays of row sums given an array of column sums? Aug 15, 2018 at 16:46
• Well I'd like to have the corresponding matrices too (to know which columns are 0's an 1's). But at least row sums arrays would be fine too. Aug 15, 2018 at 16:54

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.