Generating all unique binary vectors of length N given certain criteria

14 views (last 30 days)
Hello,
the following relates to the solution given in the question: How do I create a matrix with all binary combinations? - (mathworks.com).
I want to extend the use of this to be able to create an N binary vector of 1's and 0's that meet the following criteria:
1) No all 0 solutions
2) No vectors where the sum of the diff is greater than 2
3) Vectors where the absolute sum of the diff is greater than 1
4) Vectors whose second non-zero diff vaue is -1
5) vectors that end at 0
Translated into english, I want all possible vector combinations that either begin with a 0 or 1, but can only change from 1 to 0 and back to 1, or from 0 and to 1 but not back to 0. Here are possible candidates for N=5
0 0 0 0 1
1 1 0 0 1
0 1 1 1 1
Here are examples that I do not want:
1 0 1 0 1 -> this changes back to 0 again
0 0 0 0 0 -> this ends at 0
0 1 1 0 1-> changes back to 0 again
So some of the criteria might be redundant like 3 and 4
I got this to work via the following script:
clear
clc
N=20;
MAT_0_1=(dec2bin(0:2^N-1)-'0');
MAT_0_1_reduced=MAT_0_1;
jj=0;
for ii=1:size(MAT_0_1,1)
check_diff=diff(MAT_0_1(ii,:));
check_diff(check_diff==0)=[];
check_diff=[1 check_diff];
if sum(MAT_0_1(ii,:)==0)==N | sum(abs(diff(MAT_0_1(ii,:))))>2 | abs(sum(diff(MAT_0_1(ii,:))))>1 | (check_diff(end)==-1) | (MAT_0_1(ii,end)==0)
jj=jj+1;
save_zero(jj)=ii;
end
end
%%
MAT_0_1_reduced(save_zero,:)=[];
Where MAT_0_1_reduced gives you the final solution after removing all unwanted candidates. The problem is that for N>20 it starts becoming excessively expensive to run to the point where I tested at 30 I get the following error:
Error using *
Requested 1073741824x30 (240.0GB) array exceeds maximum array size preference. Creation of arrays greater than this
limit may take a long time and cause MATLAB to become unresponsive.
Error in dec2bin (line 60)
bits = rem(floor(d*powersOf2),2);
Error in master_q (line 5)
MAT_0_1=(dec2bin(0:2^N-1)-'0');
More information
So my question is, could there be another obfuscated hack that incorporates the criteria in the original dec2bin function so that it doesn't have to generate all possible vectors of size N but instead cuts automatically those that I dont want?

Accepted Answer

Matt J
Matt J on 28 Jun 2022
Edited: Matt J on 28 Jun 2022
N=5;
A=triu(ones(N));
B=~eye(N);
B=B(2:end-1,:);
c=nchoosek(2:N-1,2);
C=(1:N);
C=C<c(:,1)|C>c(:,2);
result=[A;B;C]
result = 11×5
1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1

More Answers (0)

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!