Próbuję zrobić wyszukiwarkę wzorców listy w Pythonie. Moim pierwszym pomysłem było pobranie pierwszej wartości z listy, a następnie znalezienie kolejnego wystąpienia tej samej wartości. Byłaby to wtedy potencjalna długość sekwencji wzoru, a następnie sprawdziłbym, czy liczby od pierwszej do drugiej liczby są równe wartości po drugiej liczbie w zakresie potencjalnej długości sekwencji wzoru.

Na przykład:

Jeśli mam tę listę

[1, 2, 6, 1, 2, 6, 1, 2, 6, 7, 8, 7, 8]

Wtedy wziąłby pierwszą liczbę 1 i wziąłby indeks drugiej 1 na liście odliczał indeks pierwszej. Więc 3 - 0 = 3, to byłaby długość wzoru. Następnie sprawdzi, czy list[:3] == list[3:3 + pattern length]. I tak dalej, aż wzorce się nie zgadzają. Ostateczny wynik to [[3, [1, 2, 6]], [2, [7, 8]]]. Byłoby lepiej mieć słownik jako wyjście, ale jeśli dwa wzorce są takie same, dictionaru nie zadziała, ponieważ nie może mieć dwóch takich samych kluczy.

Okazało się, że ta metoda nie jest zbyt skuteczna i albo nie udało mi się w pełni z moją funkcją, więc zastanawiam się, czy ktoś może mi pomóc z innym pomysłem na funkcję wyszukiwania wzorców, czy też istnieje do tego moduł Pythona.

Znalazłem ten w Internecie: https://regex101.com/r/Vdhjld/1, który robi dokładnie to, czego chcę, ale moja lista jest bardzo duża i jej użycie zajmuje dużo czasu. Jakieś pomysły na to, co powinienem zrobić?

Prosimy o komentarz, jeśli opis jest niejasny

-1
Den Fula Ankungen 19 grudzień 2019, 16:46
Podejście, które opisałeś, jest błędne. Na przykład: [1,2,1,3,1,2,1,3] wynik powinien być [[2,[1,2,1,3]]], prawda? Zamiast [[1,[1,2]],[1,[1,3]],[1,[1,2]],[1,[1,3]]]
 – 
Raj
19 grudzień 2019, 16:53
Czego byś się spodziewał, gdyby było to coś takiego jak [1, 2, 1, 2, 4, 5, 1, 2, 1, 2, 4, 5]? Co się stanie, jeśli liczby są takie same? np. [1, 1, 1, 1] to wzór [1, [1], 1, [1],...] czy [4, [1, 1, 1, 1]]?
 – 
LeoE
19 grudzień 2019, 16:53
Przepraszam, jeśli źle wyjaśniłem, tak, wynik powinien być [[2,[1,2,1,3]]] i dlatego moje podejście jest głupie.
 – 
Den Fula Ankungen
19 grudzień 2019, 17:01
Czyli nie szukasz najdłuższego wzoru, ale raczej najkrótszego wzoru?
 – 
LeoE
19 grudzień 2019, 17:04
Przepraszam, nie. Wynik powinien prawdopodobnie wynosić [[2, [1, 2, 1, 2, 4, 5]]]. Zaktualizuję moją odpowiedź. Przepraszam za zaszczyt, nie przejrzałem listy zbyt dokładnie. A może może to być [[2, [[2, [1, 2]], 4, 5]]
 – 
Den Fula Ankungen
19 grudzień 2019, 17:07

1 odpowiedź

Piszę to jako odpowiedź, ponieważ jest zbyt szczegółowa, by można było skomentować.
Myślę, że najpierw powinieneś jasno określić swoje wymagania, to nie jest trywialne pytanie i istnieje wiele rozwiązań twojego problemu, zwłaszcza jeśli jest to długa lista.

Kilka przykładów problemów, które mogą wystąpić:

Najpierw weźmy poniższą listę:

[1, 2, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1]

Istnieje wiele (wszystkie poprawne) rozwiązań znajdowania wzorców na tej liście:

  1. [3, [1, 2], 1, [3], 2, [1, 2] , 1, [3, 1, 2, 1]
  2. [1, [1, 2], 2, [1, 2, 1, 2, 3], 1, [1, 2, 1]]
  3. [1, [1], 2, [2, 1], 2, [2, 3, 1, 2, 1]]
  4. [2, [1, 2], 2, [1, 2, 3, 1, 2], 1 [1]]

Który z nich ma być „poprawną” odpowiedzią na twoje pytanie? Nawet jeśli powiemy, ten z najdłuższym podciągiem, nadal pozostały nam trzy różne rozwiązania. I to tylko przy długości listy 15 i tylko trzech różnych liczbach, im większa jest lista, tym więcej różnych rozwiązań może znajdować się na twojej liście. Jedyne rozwiązanie, jakie przychodzi mi do głowy, to arbitralny wybór jednego rozwiązania, wyszukując najdłuższy wspólny ciąg, usuwając go z listy i powtarzając, aż lista będzie pusta. Może to jednak stwarzać problemy podczas sortowania i może być bardzo powolne. Jeśli ktoś ma lepsze podejście, cieszę się, że to słyszę.

To utkwiło mi w głowie i nie miałem nic innego do roboty, więc po prostu go wypróbowałem, jest nieposortowany, trzeba by to zrobić, ale wyciąga najdłuższe powszechne wzorce. Jest to jednak rekurencyjne, więc nie wiem, czy działa na twojej długiej liście, ale może dać ci pomysł, jak go rozwiązać. Nie sądzę, że jest to zdecydowanie najszybszy możliwy sposób, to tylko jeden ze sposobów, by sobie z tym poradzić. Po prostu użyj go jako pomysłu i napisz własny kod mając to na uwadze. Oto teraz (dość długi) kod:

test = [1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 4, 5, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 5, 4]
test_1 = [1, 2, 3, 1, 2, 3, 1]
test_2 = [1, 2, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2]
test_3 = [1, 1, 1, 2, 1, 1, 1]

def pattern_finder(mylist, pattern):
    matches = []
    i = 0
    while i < len(mylist):
        if mylist[i] == pattern[0] and mylist[i:i+len(pattern)] == pattern:
            matches.append(i)
            i += len(pattern)
        else:
            i+=1
    return matches

def get_patterns(list_input, p=None):
    if type(list_input[0]) != list:
        list_input = [list_input]
    result = []
    for list_in in list_input:
        if len(set(list_in)) == 1:
            result.append([1,list_in])
            continue
        n = len(list_in)
        if n == 1:
            result.append(list_in[0])
            continue
        p_len = p
        if p == None:
            p_len = int(n/2)
        lhs = 0
        rhs = lhs + p_len
        list_split = list_in
        if p_len <= 1:
            result.append([1, list_in])
            continue
        found = False
        while lhs < n - p_len and not found:
            rhs = lhs + p_len
            while rhs <= n-p_len:
                if list_in[lhs:lhs+p_len] == list_in[rhs:rhs+p_len]:
                    found = True
                    matches = pattern_finder(list_in, list_in[lhs:lhs+p_len])
                    list_split = []

                    for i,m in enumerate(matches):
                        if i == 0 and m != 0:
                            list_split.append(list_in[0:m])
                            continue
                        if i == len(matches)-1:
                            if m+p_len != n:
                                list_split.append(list_in[m+p_len:])
                            continue
                        if m+p_len != matches[i+1]:
                            list_split.append(list_in[m+p_len:matches[i+1]])
                    result.append([len(matches), list_in[lhs:lhs+p_len]])
                    break
                rhs += 1
            lhs += 1
        if list_split == []:
            continue
        if not found:
            result += get_patterns(list_split, p_len-1)
        else:
            result += get_patterns(list_split)
    return result

print("Result:", get_patterns(test))
1
LeoE 19 grudzień 2019, 20:15
Dziękuję bardzo i za poświęcenie temu tyle czasu, jestem bardzo wdzięczny. Na pewno przyjrzę się i spróbuję zrozumieć wszystko w Twoim kodzie. Szczerze mówiąc nie wiem, czy wszystko zrozumiem, ale dziękuję. Próbowałem uruchomić go na mojej pełnej liście, prawdopodobnie działa, ale nadal działa po 20 minutach. Dzięki jeszcze raz
 – 
Den Fula Ankungen
19 grudzień 2019, 20:52
Najdłuższą powtarzającą się sekwencję można znaleźć w O(n) przy użyciu drzew przyrostków. en.wikipedia.org/wiki/Longest_repeated_substring_problem
 – 
Raj
20 grudzień 2019, 10:07