Generating all unique binary vectors of length N given certain criteria

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?

Answer 1

[Matt J]

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

[Alessandro Maria Laspina]

Perfect! Thank you.