0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So you want to find all possible (distinct) arrays of row sums given an array of column sums? $\endgroup$ – Arthur Aug 15 '18 at 16:46
  • $\begingroup$ 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. $\endgroup$ – mortalis Aug 15 '18 at 16:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your advice. I'll definitely give it a try. $\endgroup$ – mortalis Aug 17 '18 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.