Binary matrix with given row and column sum

jaydeep999997 · July 20, 2019, 5:51am

Hello everyone, I was trying one problem but was unable to get the solution of this problem , here is the problem.

Given N (number of rows) and M(number of columns), find the total number of binary matrices (containing only 0s and 1s) where sum of ith row of this matrix should be Ri and the sum of jth Column of the matrix should be Cj.

Input format : First line contains number of test cases( T ). Description of each test case is as follows, first line of each test case contains N and M number of rows and columns respectively. next line contains N integers ith integer denotes the sum if the ith row(Ri) next line contains M integers where jth integer denotes the sum of jth column(Cj)

Constraints: 1<=T<=10
1<=N <=8
1<=M<=8
0<=Ri<=M
0<=Cj<=N

Output format: (1) If there is only one solution satisfying the given criteria print this Matrix .
(2) Otherwise print the total number of possible solution satisfying the given condition.

Sample Input:

3
4 4
1 1 1 1
1 1 1 1
3 3
3 2 3
3 3 2
4 4
1 2 1 3
3 2 2 1

Sample output:
24
1 1 1
1 1 0
1 1 1
0

Explanation: In the first test case you can put only one matrix in each row and each column so in first row there are 4 possibilities in second 3 possibilities in third 2 possibilities and in the last row there is only one remaining place so answer is 4 * 3 * 2 * 1=24
In second test case there is only one possible arrangement so print the corresponding matrix.
In the third there is no possible arrangement.

mohit_6564 · July 20, 2019, 7:37am

looking at the constranints i think we can use brute-force and back-tracking to solve it , plz send the problem link.

jaydeep999997 · July 20, 2019, 7:52am

Sorry, but I am unable to open the link right now but don’t you think that brute force may give time out? By the way thanks.

pavanyewale · July 21, 2019, 6:21pm

here is the solution

github.com

pavanyewale/problem-solving/blob/master/Binary matrix with given row and column sum

#Change the input as you want 

def prim(matrix):
    for i in matrix:
        for j in i:
            print(j,end=" ")
        print()

    print("\n")
def FindMatrix(rows,cols,r,c,m,n,matrix):
    count=0
    if(rows[r]>0 and cols[c]>0):
        matrix[r][c]=1
        rows[r]-=1
        cols[c]-=1
        if(r==m-1) and (cols[c]!=0):
            matrix[r][c]=0
            rows[r]+=1
            cols[c]+=1
            return 0

This file has been truncated. show original

jaydeep999997 · July 21, 2019, 6:24pm

Thanks,They are showing the page does not found can you please look at again.

code_ankita · October 24, 2020, 9:21am

Hi! I am not getting complete code for this problem… may you look at again .