Creating all possible binary sequences for specific length under certain constraints

Question

Ben Krämer 2018-12-14

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/435779-creating-all-possible-binary-sequences-for-specific-length-under-certain-constraints

编辑： Bruno Luong 2018-12-14

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     0
   0     1
   0     0
   1     1
   1     0
   0     1
   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?

2 个评论
显示无隐藏无

Matt J 2018-12-14

编辑：Matt J 2018-12-14

在 MATLAB Online 中打开

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 2018-12-14

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 2018-12-14

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/435779-creating-all-possible-binary-sequences-for-specific-length-under-certain-constraints#answer_352430

编辑：Bruno Luong 2018-12-14

在 MATLAB Online 中打开

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