wyszukiwania algorytm

Question

ja szukam skutecznego algorytmu wyszukiwania, aby uzyskać najdłuższynajkrótszą powtarzane w kolekcji (~ 2k liczb całkowitych), gdzie moja kolekcja wykonana jest tylko z tego powtarzającego się wzorca (nie ma hałasu pomiędzy powtarzającymi się wzorami), ale ostatnie pojawienie się wzoru może być niepełne.

Przykłady: ja mam: [2,4,1, 2,4,1, 2,4,1, 2,4,1, 2,4,1]
które chciałbym OTRZYMA: [2,4,1]

mam: [21,1,15,22, 21,1,15,22, 21,1,15,22, 21,1,15]
Chciałbym OTRZYMA: [21,1,15,22]

mam: [3,2,3,2,5]
Chciałbym otrzymywać: [] (brak wzorca)

(miejsca dodane tylko dla czytelności)

Answer 1

Bardzo prosty algorytm do przodu będzie wyglądać następująco (w Pythonie, ale nie powinno być problemu, aby przetłumaczyć JavaScript):

def check(a, width): 
    '''check if there is a repeated pattern of length |width|''' 
    for j in range(width, len(a)): 
    if a[j] != a[j-width]: 
     return False 
    return True 

def repeated(a): 
    '''find the shortest repeated pattern''' 
    for width in range(1, len(a)): 
    if check(a, width): 
     return a[:width] 
    return [] 

ten powinien być również dość wydajny, gdyż większość czasu pętli w check() powróci bezpośrednio w pierwszej iteracji, tak że w zasadzie tylko iteruje się po liście raz.

Answer 2

Spróbuj zbudować początkowe grupowanie zaczynając od początku dodając numer do grupy, aż dojdziesz do numeru, który jest taki sam jak pierwszy w grupie (poprzedni numer kończy się wzór). Użyj tego jako wzorca testowego i przejdź przez proces dopasowywania wzoru, aż do wystąpienia błędu. Jeśli dopasujesz całą kolekcję (ze specjalną obsługą wzorów końcowych), która jest jednym kandydatem. Wróć do miejsca, w którym znalazłeś swój początkowy mecz, a następnie kontynuuj budowanie swojej grupy, aż dojdziesz do innej liczby pasującej do pierwszej we wzorcu. Powtarzaj, zastępując kandydata, gdy znajdziesz dłuższy. Kiedy twój wzór jest tej samej długości co przystanek kolekcji (ten nie pasuje). Jeśli masz kandydata, który będzie najdłuższym wzorem.

Answer 3

Myślę, że możesz podejść do tego problemu, biorąc pod uwagę okres wzorca. Okres sekwencji A [] jest najmniejszą liczbą całkowitą T taką, że A [i + T] = A [i] dla wszystkich i. W twoim przypadku, gdy znajdziesz okres T, skończysz, ponieważ A [0..T-1] jest najkrótszym wzorem, którego szukasz. Zacznij więc od małych możliwych okresów T = 1 i sprawdź, czy sekwencja spełnia okresową właściwość. Jeśli tak, skończyłeś (tak się dzieje tylko wtedy, gdy wszystkie elementy są identyczne). Dla każdego większego T należy sprawdzić, czy A [i + T] = A [i] dla i = 0..A.len-T-1. To tylko prosta pętla.

Answer 4

Możesz zoptymalizować wyszukiwanie, zauważając, że długość kolekcji musi być wielokrotnością długości wzoru. Jeśli twoja kolekcja ma rozmiar główny, jedyną możliwą długością wzoru jest 1, tzn. Wszystkie elementy muszą być identyczne!