how can i have all possible configuration of binary(digital) 3*4 matrix for for given rows and columns constrains?

hi

the binary matrix with size 3*4 can have 2^12 configuration but i have constrains for each row and each column . an example of constrain is r1=[0 1 0 1;1 1 1 1;0 0 0 0] which means row 1 of matrix 3*4 can only have these three configuration and another example of constrain is c2=[1;0;0;0 0;0;1;1] which means column 2 can only have these two configuration.(we have c1 c2 c3 c4 and r1 r2 r3 r4)

now with given constrains,i want all possible configurations in a 3D matrix with size 3*4*n. (n = number of possible configuration). can anybody help me? (the actual matrix is 15*24 but i said 3*4 for simplification)

[Matt J]

the actual matrix is 15*24

Without constraints that will require 2.1873e+99 GB storage. Your constraints will reduce this somewhat, but do you know they will be enough to bring the number of combinations down to realistic RAM requirements? What math can you show us that proves this?

[g davami]

without constrains, it has 2^360 =10^108 possible configurations. with only the rows constrains, possible configurations reduce the to about 10^60 (Cartesian product of possible configuration of each row.)

and with only the columns constrains, possible configurations reduce the to about 10^61 (Cartesian product of possible configuration of each column). i dont know hom many possible configurations it will have with both constrains at same time, but even if it is impossible (due hardware requirements) i want to know the matlab code, so i show my teacher it is impossible due hardware requirements.

in short how can i have all possible configuration of binary matrix (for example 3*4) for for given rows and columns constrains?

Answer 1

[Aastha]

Hi @g davami,

I understand that you want to generate all possible configurations of a binary matrix of size 3*4*n with the constraints on the rows and columns of the matrix and where “n” is the number of possible configurations.

You may refer to the steps mentioned below to get all the possible configurations:

1. First, define the size of M × N matrix, where M is the number of rows and N is the number of columns and generate the number of possible combinations. For this example, let M=3 and N=4:

M = 3; %number of rows
N = 4; %number of columns
TP = 2.^(M*N); %Total Possible combinations

2. Next, store the row constraints “rc” and column constraints “cc” in cell arrays. Each entry corresponds to constraints for specific rows or columns.

rc = {[0 1 0 1;1 1 1 1;0 0 0 0], [], []};  % Row constraints 

cc = {[], [1,0,0;0,1,1], [], []};          % Column constraints 

3. Loop through all possible binary matrices by converting each integer from 0 to TP-1 into a binary string and then reshape it into a M × N matrix. The code below illustrates this:

cnt = 0; 

for tp = 1:TP 
    matrix = reshape(dec2bin(tp-1,M*N) - '0', [M, N]);  % Generate binary matrix 
    if isValid(matrix, rc, cc) 
        valid_combinations(:,:,cnt) = matrix;  % Store valid matrices 
        cnt = cnt + 1; 
    end 
end 

The “isValid” function checks if the matrix satisfies row and column constraints:

function [valid] = isValid(matrix, rc, cc) 
    valid = 1;  % Assume matrix is valid 
    % Check row constraints 
    for r = 1:length(rc) 
        if ~isempty(rc{r}) 
            [dist,~] = min(sum(matrix(r,:) ~= rc{r}, 2));  % Check mismatches 
            if dist > 0 
                valid = 0;  % Invalid if any row constraint fails 
                break; 
            end 
        end 
    end 
    % Check column constraints (if rows are valid) 
    if valid == 1 
        for c = 1:length(cc) 
            if ~isempty(cc{c}) 
                [dist,~] = min(sum(transpose(matrix(:,c)) ~= cc{c}, 2));  % Check column mismatches 
                if dist > 0 
                   valid = 0;  % Invalid if any column constraint fails 
                   break; 
                end 
            end
        end
    end 
end 

This method generates and stores all valid matrices. For larger matrices, consider saving them to disk instead of memory as the number of possibilities grow exponentially.

For more information on the functions used in the above code, refer to the link of the MathWorks Documentation mentioned below:

-transpose:

https://www.mathworks.com/help/matlab/ref/double.transpose.html

-isvalid:

https://www.mathworks.com/help/matlab/ref/handle.isvalid.html

-isempty:

https://www.mathworks.com/help/matlab/ref/double.isempty.html

I hope this helps!