0

I have a list containing only True and False values. I am looking for a pattern when the elements of the list changes from True to False or vise versa more than 3 times.

Example (T is used for True and F for False for abbreviation):

List = [T, T, T, F, F, F, T, F, T, F, T, T, T, T]

What I want to detect is : [F, T, F, T, F, T] and its starting index in the original list.

Please note that the pattern is not fixed. It may be [F, T, F, T, F, T] or [T, F, T, F, T].

If you have any idea to accomplish this task efficiently, please let me know.

If fact, I need this detection to be done in real-time. I mean, the List is being made by getting data from another source (timestamp is 0.5 second). And I need to detect the above mentioned pattern in the List. In you are aware how to solve this problem (either real time or not), please let me know.

Mohammad
  • 775
  • 1
  • 14
  • 37
  • 1
    Do you want the index of only the longest pattern or all such patterns found? – Mehul Gupta May 18 '20 at 04:16
  • I don't think this is going to help you for whatever you are doing but I have to say for effective pattern recognitions you probably need an unsupervised neural network – Mia May 18 '20 at 04:18
  • Does this answer your question? [Checking if list is a sublist](https://stackoverflow.com/questions/35964155/checking-if-list-is-a-sublist) – Joshua Varghese May 18 '20 at 04:22
  • @pkqxdd Errr... this is only about a fixed sequence (`FTFTFT`). All they essentially need is some hardcoded variant of a DFA to match the pattern `(FT){3}`. Why would you suggest a NN? – Mateen Ulhaq May 18 '20 at 04:25
  • If the subsequence you were looking for was longer, and you knew the statistical characteristics of your data, you might be able to go faster by looking for low-probability runs from your subsequence, to go from amortized `O(kn)` to something smaller... but the subsequence is so short that I think some simple for loops are enough. See also: https://en.wikipedia.org/wiki/String-searching_algorithm – Mateen Ulhaq May 18 '20 at 04:32
  • I want to get all occurrences (not only biggest). Please note that the pattern is not fixed. It may be FTFTFT or TFTFT. @MehulGupta – Mohammad May 18 '20 at 04:37

2 Answers2

0

Well, you could make each list into a string:

newlist=['T' if x is True else 'F' for x in mylist]
newstring=''.join(newlist)

Then find the position of the match to 'FTFTFT' as described in the accepted answer to this question.

Igor Rivin
  • 4,632
  • 2
  • 23
  • 35
0

The problem is analogous to finding the subarray of maximum length whose sum is 0 and can be approached in a similar manner:

T = True
F = False

List = [T, T, T, F, F, F, T, F, T, F, T, T, T, T] 


def max_toggle_subarray(arr):
    start = 0
    max_len = 0

    for indexI, i in enumerate(arr):
        length = 0
        for indexJ, j in enumerate(arr[indexI:-1]):
            curr = j
            length += 1
            predict = False if curr else True # Toggle and predict next
            if predict == arr[indexI + indexJ + 1]:
                if length >= max_len:
                    max_len = length
                    if indexJ == 0: start = max(start, indexI + indexJ) # We dont update start index on every iteration
                    end = indexI + indexJ + 1
            else:
                break
    return start, end


# test array
print("Length of the longest subarray is starting at % d until % d" % max_toggle_subarray(List))

It might be possible to reduce time complexity to O(n) with a approach similar to - find the Largest Sum Contiguous Subarray

Luv
  • 386
  • 4
  • 15