Clear Filters
Clear Filters

Find longest pattern of [1 0] in array.

8 views (last 30 days)
I have Bits0 array of 1's and 0's. I would like to get the start/stop indices of the largest sequence of 1 0's. Actually, I expect at least 4 repetitions of [1 0].
I know there are file exchange functions that I have heard about (but I am in an air-gap environment). Is it possible to get just a few more lines of code to solve this problem? Here is what I have so far.
b_PATTERN = [1 0 1 0 1 0 1 0 ];
Bits0 = [0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0];
patternLocs = uint32(strfind(Bits0, b_PATTERN ))
patternLocs = 1×17
6 8 10 12 22 24 26 28 30 32 34 36 38 47 49 51 53
if isempty(patternLocs)
Bits0_start = []; % cannot find pattern
end
patternDiffLocs = diff( patternLocs )
patternDiffLocs = 1×16
2 2 2 10 2 2 2 2 2 2 2 2 9 2 2 2
% Problem now reduced to finding longest pattern of 2's.
% Need patIdx = 5; num_2s = 8
% Need Bits0_start = 22; Bits0_stop = 45 (at least close - counted by hand)

Accepted Answer

Walter Roberson
Walter Roberson on 5 Oct 2022
The below code will find all of the subsets of maximum length (I do not assume that it will be unique)
The union() are present because the pattern can be ended by having immediately the wrong bit at an end of a subset, but also by having the right next bit at the end of a subset but having the wrong bit on the other side of that.
repeat_count = 4;
b_PATTERN = repmat([1 0], 1, repeat_count);
Bits0 = [0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0];
Bits0_start = union(strfind([0 0 Bits0], [0 0 b_PATTERN]), strfind([1 Bits0], [1 b_PATTERN]))
Bits0_start = 3×1
6 22 47
Bits0_stop = union(strfind([Bits0 1 1], [b_PATTERN 1 1]), strfind([Bits0 0], [b_PATTERN 0])) + length(b_PATTERN) - 1
Bits0_stop = 1×3
19 45 60
durations = Bits0_stop(:) - Bits0_start(:) + 1
durations = 3×1
14 24 14
longest_idx = find(durations == max(durations))
longest_idx = 2
T = table(Bits0_start(longest_idx).', Bits0_stop(longest_idx).', 'VariableNames', {'Start', 'Stop'})
T = 1×2 table
Start Stop _____ ____ 22 45
  5 Comments
Paul Hoffrichter
Paul Hoffrichter on 7 Oct 2022
No specialized Matlab code here. Just a simple, elegant, and most probably very efficient algorithm good in any programming language. Not sure how you thought of it! Wish I had. Thank you!
(If this is an algorithm that is in a textbooks, I would appreciate the reference - might be worth getting it for other algorithms.)
Re: "you can find rising edges by looking for places that start with the appropriate low conditions, and by looking for places that end with the appropriate high conditions"
I think I see what you are getting at here. With noisy signals, I have been determining a threshold to convert to 1's and 0's. Then I take the diff to get the 0-crossings. Then I have to deal with 0-crossings that shouldn't be there due to noise. I think using this technique, I'll be able to find the start/stop of a burst of energy without a diff and without too much concern about the extra 0-crossings (but not positive - will have to think about this more). But now, I am expecting to reduce the number of bogus 0-crossings significantly. Thanks so much @Walter Roberson!

Sign in to comment.

More Answers (0)

Products


Release

R2020a

Community Treasure Hunt

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

Start Hunting!