Creating all possible binary sequences for specific length under certain constraints

I want to create a Matrix of all possible binary sequences with the lenght of 96 (number of quarter-hours per day) that meet my constraints.

My constraints are for example:

• At least x values of the sequence have to be 1
• No more than 5 repeating 0s are allowed

Example with n=3:

output = dec2bin(2^n-1:-1:0)-'0'
output =
     1     1     1
     1     1     0
     1     0     1
     1     0     0
     0     1     1
     0     1     0
     0     0     1
     0     0     0

Constraints:

• At least 2 Values of the sequence have to be 1
• No more than 2 repeating 1s allowed

output =
     1     0     1

What I planned to do is to generate all possible combinations and afterwards use the constraints on that Matrix and filter out the sequences that don't pass my constraints.

When I try to generate all the possible combinations (2^96) using this:

output = dec2bin(2^96-1:-1:0)-'0'    

I obviously get: Maximum variable size allowed by the program is exceeded. Since the Matrix would be way to big.

By adding the constraints, I am hoping to get a manageable Matrixsize.

Does anyone have an idea?

[Matt J]

By adding the constraints, I am hoping to get a manageable Matrixsize.

Doubtful. You would need at least one of the constraints by itself to significantly narrow the pool. For example,

• At least x values of the sequence have to be 1

If x were 93, then this would right away reduce the pool to a more manageable number,

>> nchoosek(96,93)

ans =

      142880

What do you plan to do with all of these combinations if you could generate them?

[Guillaume]

In addition to matt's comment, I don't even understand the example with n=3. How is [1 1 0] not allowed under the constraints:

• At least 2 Values of the sequence have to be 1. yes, it's got 2
• No more than 2 repeating 1s allowed. yes, it hasn't got more than 2

Answer 1

[Bruno Luong]

This code works for toy dimension(s), if you take n up to 96 you might have memory issue as people have rightly warned you.

n = 5;
x = 3;
P0 = [0 0]; % Pattern of 0 not allowed

A = [];
for k=x:n
    C = nchoosek(1:n,k);
    m = size(C,1);
    R = repmat((1:m)',1,k);
    Ak = accumarray([R(:) C(:)],1,[m n]);
    % filter out those who do not meet the second criteria
    S = [Ak'; ones(1,m)];
    i = strfind(S(:).', P0);
    Ak(ceil((i-1)/(n+1)),:) = [];
    A = [A; Ak];
end
A