- At least x values of the sequence have to be 1
Creating all possible binary sequences for specific length under certain constraints
17 views (last 30 days)
Show older comments
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.
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 Comments
Matt J
on 14 Dec 2018
Edited: Matt J
on 14 Dec 2018
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,
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
on 14 Dec 2018
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
Accepted Answer
Bruno Luong
on 14 Dec 2018
Edited: Bruno Luong
on 14 Dec 2018
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
0 Comments
More Answers (0)
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!