How can I make a pattern of binary digits like this?
4 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
Luqman Saleem
am 25 Jul. 2017
Kommentiert: Jan
am 27 Jul. 2017
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?
1 Kommentar
John D'Errico
am 25 Jul. 2017
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.
Akzeptierte Antwort
Guillaume
am 25 Jul. 2017
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))
1 Kommentar
Jan
am 27 Jul. 2017
This requires the temporary arrays bits and rows as well as [rows(:), bits(:)], in total twice as large as the resulting output.
Weitere Antworten (2)
Star Strider
am 25 Jul. 2017
Bearbeitet: Star Strider
am 25 Jul. 2017
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
1 Kommentar
Jan
am 25 Jul. 2017
Bearbeitet: Jan
am 27 Jul. 2017
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;
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
0 Kommentare
Siehe auch
Kategorien
Mehr zu Logical finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!