Znajdowanie wzorców na liście

Question

Obecnie szukam sposobu na znalezienie wzorców na liście liczb całkowitych, ale metoda, którą zamierzam użyć, będzie miała zastosowanie do łańcuchów i innych list z różnymi elementami oczywiście. Teraz pozwól mi wyjaśnić, czego szukam.

Chcę znaleźć najdłuższy powtarzający się wzór na liście liczb całkowitych. Na przykład:

[1, 2, 3, 4, 1, 2, 3] 
# This list would give 1, 2, 3 

Nakładające się wzory należy wyrzucić. (Nie jest pewne)

[1, 1, 1, 1, 1] 
# Should give 1, 1 Not 1, 1, 1, 1 

Oto co mi nie pomoże.

Finding patterns in a list (nie rozumiem logikę pierwszej odpowiedzi, bardzo mało wyjaśnień. A po drugie odpowiedź rozwiązuje problem tylko wtedy, gdy wzór jest znany przed rozwiązywania.)

Finding integer pattern from a list (wzór jest podany i numer występowania Inaczej niż moje pytanie.)

Longest common subsequence problem (Większość osób zajmowała się tym problemem, ale nie jest to bliskie mojej, potrzebuję kolejnych elementów podczas wyszukiwania wzoru, jednak w tym przypadku oddzielne elementy również są liczone jako podciągi.)

Oto, co próbowałem.

def pattern(seq): 
    n = len(seq) 
    c = defaultdict(int) # Counts of each subsequence 
    for i in xrange(n): 
     for j in xrange(i + 1, min(n, n/2 + i)): 
      # Used n/2 because I figured if a pattern is being searched 
      # It cant be longer that the half of the list. 
      c[tuple(seq[i:j])] += 1  
    return c 

Jak widać, to wyszukuje wszystkie listy zagnieżdżone i sprawdzić powtórzeń. Uważam, że to podejście jest trochę naiwne (i nieskuteczne) i potrzebuję lepszego sposobu. Proszę pomóż mi. Z góry dziękuję.

Uwaga 1: Lista jest z góry ustalona, ​​ale z powodu błędów mojego algorytmu mogę tylko sprawdzić niektóre części listy przed zamrożeniem komputera. Wzorzec, który próbuję znaleźć, może być dłuższy niż połowa listy wyszukiwania. Może być nawet dłuższy niż sama lista wyszukiwania, ponieważ szukam tylko części oryginalnej listy. Jeśli przedstawisz lepszą metodę niż Używam, mogę przeszukiwać większą część oryginalnej listy, więc będę miał większą szansę na znalezienie wzoru. (Jeśli takowy istnieje).

Uwaga2: Oto część listy, jeśli chcesz przetestować ją samodzielnie. Wygląda na to, że istnieje pewien wzór, ale nie mogę być tego pewien, zanim przetestuję go niezawodnym kodem. Sample List

Uwaga 3: Podchodzę do tego jako poważny problem eksploracji danych. I spróbuje się dowiedzieć, czy robisz długie wytłumaczenie. Wydaje się, że jest to znacznie ważniejszy problem niż LCS, jednak LCS jest znacznie bardziej popularny: D Ta metoda, którą próbuję znaleźć, przypomina metody stosowane przez naukowców do wyszukiwania wzorców DNA.

Answer 1

Kodeks

Ignorując „nie nakładający” wymóg, oto kod użyłem:

def pattern(seq): 
     storage = {} 
     for length in range(1,len(seq)/2+1): 
       valid_strings = {} 
       for start in range(0,len(seq)-length+1): 
         valid_strings[start] = tuple(seq[start:start+length]) 
       candidates = set(valid_strings.values()) 
       if len(candidates) != len(valid_strings.values()): 
         print "Pattern found for " + str(length) 
         storage = valid_strings 
       else: 
         print "No pattern found for " + str(length) 
         return set(filter(lambda x: storage.values().count(x) > 1, storage.values())) 
     return storage 

Korzystanie że znalazłem 8 różnych wzorców długości 303 w zestawie danych. Program również działał dość szybko.

Pseudokod Wersja

define patterns(sequence): 
    list_of_substrings = {} 
    for each valid length: ### i.e. lengths from 1 to half the list's length 
     generate a dictionary my_dict of all sub-lists of size length 
     if there are repeats: 
      list_of_substrings = my_dict 
     else: 
      return all repeated values in list_of_substrings 
    return list_of_substrings #### returns {} when there are no patterns