How can I make a pattern of binary digits like this?

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)

0 0 1 1  

0 1 0 1  

0 1 1 0  

1 0 0 1

1 0 1 0

1 1 0 0

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

[John D'Errico]

There are at least 3 trivial solutions for small M and N that I can think of off the top of my head. But I have found that NOBODY ever gives an example that is the same size as their real problem.

For example, one trivial solution I might offer would fail whenever M is greater than around 15. Other schemes might go a bit higher, but will eventually fail.

In fact, ANY scheme will fail for even moderately large M and N. For example, I can be pretty certain that nothing you do will solve this problem when M=50, and N=25, as to create that array would require literally a petabyte or more of memory, even if bit level storage was used to store the entire array.

So if you realistically want any useful help at all, then you need to tell people the true expected sizes of M and N.

Answer 1

[Guillaume]

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))

[Jan]

This requires the temporary arrays bits and rows as well as [rows(:), bits(:)], in total twice as large as the resulting output.

Answer 2

[Star Strider]

Try this:

M = 4;
N = 2;
A = dec2bin(1:2^M-1)-'0';
Result = A(sum(A,2)==N,:);

Result =
     0     0     1     1
     0     1     0     1
     0     1     1     0
     1     0     0     1
     1     0     1     0
     1     1     0     0

[Luqman Saleem]

Thank you so much. Can you please tell me what exactly

-'0'

in 3rd line is doing here? Sorry I am new to MATLAB.

Answer 3

[Jan]

The idea is to get all ways to select N values out of 1:M. This is cheaper than to create all combinations at first and removing the ones with the wrong number of bits:

N = 2;
M = 4;
C = nchoosek(1:M, N);
R = zeros(size(C, 1), M, 'uint8');
R(C) = 1;

This can be done faster using https://www.mathworks.com/matlabcentral/fileexchange/26190-vchoosek:

C = VChooseK(uint8(1):uint8(M), N);

Because this stores the indices in an UINT8 array, it occupies one byte per index only instead of 8 for doubles.

Remember John's important comment: Many users in the forum tried to do such things with M = 50. Use nchoosek(M, N) to check, if the problem can be solved with your computer.

[EDITED] Timings (R2016b/64, Core2Duo, Win7, 6GB RAM):

M = 20;
N = 10;

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

tic
C    = nchoosek(1:M, N);
R    = zeros(size(C, 1), M, 'uint8');
R(C) = 1;
toc

tic
C    = nchoosek(uint8(1:M), N);
R    = zeros(size(C, 1), M, 'uint8');
R(C) = 1;
toc

tic
R = VChooseK(uint8(1):uint8(M), N);
toc

 Elapsed time is 2.295773 seconds.   % NCHOOSEK, SORTROWS, ACCUMARRAY
 Elapsed time is 1.985920 seconds.   % NCHOOSEK(double)
 Elapsed time is 1.572937 seconds.   % NCHOOSEK(uint8)
 Elapsed time is 0.038843 seconds.   % C-mex