CODEWITHSUNDEEP
matlabmatrix
valli
valli

Reputation: 43

all possible binary matrices with fixed number of 1

Hi can I generate all possible binary matrices with fixed number of 1's in each matrix of given order in matlab.

For example, all 4x4 matrices with two 1's in each matrix, [1 1 0 0;0 0 0 0;0 0 0 0;0 0 0 0],[1 0 0 0;0 1 0 0;0 0 0 0;0 0 0 0], [1 0 0 0;0 0 0 0;1 0 0 0;0 0 0 0]

Upvotes: 2

Views: 131

Answers (3)

Luis Mendo
Luis Mendo

Reputation: 112679

Here's a vectorized solution:

N = 4; % matrix size
M = 2; % number of ones
ind = nchoosek(1:N^2, M); 
result = zeros(N,N,size(ind,1));
result(bsxfun(@plus, ind, (0:size(ind,1)-1).'*N^2)) = 1;

Each matrix is a 3rd-dim slice of result:

>> result
result(:,:,1) =
     1     0     0     0
     1     0     0     0
     0     0     0     0
     0     0     0     0
result(:,:,2) =
     1     0     0     0
     0     0     0     0
     1     0     0     0
     0     0     0     0
···
result(:,:,120) =
     0     0     0     0
     0     0     0     0
     0     0     0     1
     0     0     0     1

Upvotes: 2

OmG
OmG

Reputation: 18838

You can find all subsets of indices with the length of 2, and then replace 1s in that indices. First find subsets with specidfied length using the following code:

function subsets = get_subset(N, c)
   indices = dec2bin(1:(2 ^ N - 1)) - '0';   % indices of all subsets
   counter = sum(indices, 2);                % number of elements in subsets
   subsets = indices(find(counter == c), :);  % select appropriate subsets
end

Then, get all possible indices and replace 1s:

n = 10; k = 2;
A = zeros(n);
all = cell(1,nchoosek(n,k));
subsets = get_subset(numel(A), k);
len = size(subsets,1);
for i = 1:len
    temp = A;
    temp(find(subsets(i,:) == 1)) = 1;
    all{i} = temp;
end

UPDATE: As a matter of efficiency, instead of get_subset, you can use combnk as a native function in matlab.

n = 10; k = 2;
A = zeros(n);
all = cell(1,nchoosek(n,k));
subsets = combnk(numel(A), k);
len = size(subsets,1);
for i = 1:len
    temp = A;
    temp(find(subsets(i,:) == 1)) = 1;
    all{i} = temp;
end

Upvotes: 0

Finn
Finn

Reputation: 2343

if you want to create every combination there should be (16x15)/2 combinations (Matsize*Matsize-1)/2), because you can choose the fist on anywhere, the second one anywhere but where the first is and devied by 2 because 1-2 is the same as 2-1. Be aware that if you want to have 3 '1' for example you would have to have 16x15x14/6 (as 3 facotrial). There is a MATLAB function for getting every combination and then you just have to create every matrix while using the combinations as indices (in a 4x4 matrix you can address Matrix(2,1) as Matrix(5) ). 

C = combnk(1:16,2); %16 elements and 2 '1'
Matrizes = zeros(length(C),4,4);

for i=1:size(Matrizes,1)
    Matrizes(i,C(i,:))=1;
end

There is most certainly a way to get rid of the for loop, but as I dont know how performance critical this is I just went for the easy way.

Upvotes: 0

Related Questions