MATLAB: How to make a pattern of binary digits like this

binaryhomework

Let I have an integer N that gives sum of all bits in a given row (e.g. if a row is [0 0 1 1] than N=2) and another integer M that counts number of columns in a row (in above example M=4). M is always greater than N

What I want is to make a code that will give me an array of something like this: (lets say N=2 and M=4)

In short I want to arrange bits in increasing order. Can someone help me making this code for given N and M?

Best Answer

Another solution, which does not involve generating all bit patterns and then discarding the unwanted ones:

M = 4;
N = 2;
bits = nchoosek(1:M, N);
rows = repmat(1:size(bits, 1), N, 1)';
result = sortrows(accumarray([rows(:), bits(:)], 1))

Related Solutions

MATLAB: How to generate an array of binary data of this form

It might not be the most beautiful algorithm in the world, but this works (on 64 bit MATLAB) for even N values up to at least

N = 20, giving 184756 rows in 15 seconds
N = 22, giving 705432 rows in 106 seconds.
N = higher might be possible, if you are patient enough and have enough memory...

but keep in mind that at some point you will simply run out of memory.

It is easy to check that all rows sum to the requested value. In contrast there is no obvious way to check if any rows are missing, but I did notice that the number of rows matches exactly with OEIS A000984, which might have some relevance.

N = 12;
M = [0,1;1,0];
for k = 3:N
    R = size(M,1);
    M = [zeros(R,1),M;ones(R,1),M;M,zeros(R,1);M,ones(R,1)];
    M = unique(M(sum(M,2)<=N/2,:),'rows');
end
M = M(sum(M,2)==N/2,:);

For N=12 this gives:

>> size(M)
ans =
   924    12
>> M
ans =
     0     0     0     0     0     0     1     1     1     1     1     1
     0     0     0     0     0     1     0     1     1     1     1     1
     0     0     0     0     0     1     1     0     1     1     1     1
     0     0     0     0     0     1     1     1     0     1     1     1
     0     0     0     0     0     1     1     1     1     0     1     1
     0     0     0     0     0     1     1     1     1     1     0     1
     0     0     0     0     0     1     1     1     1     1     1     0
     0     0     0     0     1     0     0     1     1     1     1     1
     0     0     0     0     1     0     1     0     1     1     1     1
... lots of rows here
     1     1     1     1     0     1     0     0     1     0     0     0
     1     1     1     1     0     1     0     1     0     0     0     0
     1     1     1     1     0     1     1     0     0     0     0     0
     1     1     1     1     1     0     0     0     0     0     0     1
     1     1     1     1     1     0     0     0     0     0     1     0
     1     1     1     1     1     0     0     0     0     1     0     0
     1     1     1     1     1     0     0     0     1     0     0     0
     1     1     1     1     1     0     0     1     0     0     0     0
     1     1     1     1     1     0     1     0     0     0     0     0
     1     1     1     1     1     1     0     0     0     0     0     0

PS: of course recursive algorithms for generating permutations are simple but when I tried some with added short-circuit behavior for repeated rows, they were significantly slower than the above loop.

MATLAB: Generating combination of binary numbers

nchoosek outputs the indices in your desired ordering, so it's easy:

N = 5, M = 2;  %demo data
cols = nchoosek(1:N, M);
A = zeros(size(cols, 1), N);
A(sub2ind(size(A), repmat((1:size(A, 1))', 1, M), cols)) = 1

Best Answer

Related Solutions

MATLAB: How to generate an array of binary data of this form

MATLAB: Generating combination of binary numbers

Related Question