CODEWITHSUNDEEP
arraysmatlabmatrix
m2016b
m2016b

Reputation: 544

MATLAB : How can I generate a random binary matrix with a specific number of 1s in each row and in each column?

I would like to generate a binary matrix A of dimension m * n with a unique number J of 1s on each column of the matrix and a unique number K of 1s on each row of the matrix.

For example, for a binary matrix A of dimension m * n = 5 * 10 with J = 3 and K = 6 we may obtain the following matrix:

1 0 1 1 1 0 1 1 0 0 
0 1 1 0 0 1 1 0 1 1 
1 1 0 1 1 1 0 1 0 0 
0 1 1 0 1 0 1 0 1 1 
1 0 0 1 0 1 0 1 1 1

This answer by Luis Mendo, gives just the specific number of 1s on each column. In my case I'm trying to add the option of the specific factor of 1s on each column and on each row, which can be a different number.

How can I construct this matrix?

Upvotes: 0

Views: 392

Answers (1)

blupp
blupp

Reputation: 337

I made this just for fun. It can get stuck, so it doesn't work all the time. For the values in your example, the function found a matrix in about 40 % of the runs. You might want to tinker a bit with max_iterations. If it's too small, the probability of finding a matrix goes down, but if it's too large it's really time consuming.

Note: I wrote this in python and haven't run it in matlab, so there might be typos.

function A = generate_matrix(m,n,J,K, max_iterations)

if nargin < 5
    max_iterations = m*K*4; 
end

% Check if it's possible to create matrix:
if (m*K ~= n*J)
    error('Matrix not possible')
end

A = falses(m,n);

allowed_rows = 1:m;
allowed_cols = 1:n;
too_many_iterations = false;
counter = 0;

while ~isempty(allowed_rows) && ~too_many_iterations

    % pick random row and column from the ones that don't have enough ones
    row_index = allowed_rows(randi(length(allowed_rows)));
    col_index = allowed_cols(randi(length(allowed_cols)));

    A(row_index, col_index) = true;

    % Update allowed_rows and allowed_cols
    allowed_rows = find(sum(A,2) < K);
    allowed_cols = find(sum(A,1) < J);

    % Keep track of number of iterations
    counter = counter + 1;
    too_many_iterations = counter > max_iterations;
end

if ~isempty(allowed_rows)
    warning('Matrix not found!')
    A = [];
end

end

The function will start with a matrix of zeros and randomly pick a row and column that doesn't have enough ones and place a one at that location, then pick a new row and column and so on until there are no rows left. The reason it doesn't work all the time, is that it can reach a dead end. For example, with m=3, n=6, J=2 and K=4, the following matrix is a dead end, since the only row without four ones is row 1, the only column without two ones is column 3, but A[1,3] already is one.

[1, 0, 1, 1, 0, 0;
 1, 1, 0, 0, 1, 1;
 0, 1, 0, 1, 1, 1]

Upvotes: 2

Related Questions