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.