I'm actually working in a piece of code that will take a generic enumeration and a given length and will return the most frequent pattern found in the enumeration of the specified length and how many times it appears.
My method therefore has the following signature:
public static IEnumerable<T> ExtractFixedLengthPatter<T>(IEnumerable<T> source, int length, out int timesFound) { ... }
The way I've implemented this is as follows (I won't post the corresponding code, its a little long):
Given, lets say, an enumerable of ints:
121234161221
and a pattern length of2
I build the following tree:[1] -- [2] {count: 3} -- [6] {count: 1} [2] -- [1] {count: 2} -- [2] {count: 1} -- [3] {count: 1} [3] -- [4] {count: 1} [4] -- [1] {count: 1} [6] -- [1] {count: 1}
The way I build this tree is that I iterate the stream and in each iteration I create a custom iterator that takes the first length
items from the current position and populates the tree:
1rst outer iteration: {1}
Fixed length iterator: {1}
{2}
2nd outer iteration: {2}
Fixed length iterator: {2}
{1}
And so on...
Then, I simply identify the final node with maximum count and traverse back up the tree obtaining the most frequent pattern reversed. I reverse the pattern and I'm done.
This algorithm works really well and is pretty fast. The problem is that a co-worker is claiming it has a serious bug. Consider the following case:
111111
Its obvious the most frequent pattern of length 2
is 11
. The question is, how many times does it appear in the enumeration? My coworker claims the correct answer is 3
:
111111
11
11
11
My algorithm returns 5
:
111111
11
11
11
11
11
Which one is the correct answer? I'm inclined to believe its 5
but if its 3
, does anyone see an easy way I can adapt or change the algorithm to discern this kind of situation?
11
in111111
is a matter of convention, decide if it is 3 or 5, if overlapping patterns count or not.