Algorytm O (nlogn) - znajdź trzy równomiernie rozmieszczone w ciągu binarnym

Miałem to pytanie w teście Algorytmów wczoraj i nie mogę znaleźć odpowiedzi. Doprowadza mnie to do szału, bo było warte około 40 punktów. Wydaje mi się, że większość zajęć nie rozwiązała go poprawnie, ponieważ nie wymyśliłem rozwiązania w ciągu ostatnich 24 godzin.

Mając dowolny ciąg binarny o długości n, znajdź trzy równomiernie rozmieszczone w ciągu ciągu, jeśli istnieją. Napisz algorytm, który rozwiąże to w czasie O (n * log (n)).

Tak więc ciągi takie jak te mają trzy ciągi, które są „w równych odstępach”: 11100000, 0100100100

edycja: Jest to liczba losowa, więc powinna być w stanie pracować dla dowolnej liczby. Przykłady, które podałem, miały zilustrować właściwość „równomiernie rozmieszczonych”. Więc 1001011 to poprawna liczba. Z 1, 4 i 7 to te, które są rozmieszczone w równych odstępach.

Wreszcie! Idąc za tropami w odpowiedzi sdcvvc , mamy to: algorytm O (n log n) dla problemu! Jest to również proste, gdy to zrozumiesz. Rację mieli ci, którzy odgadli FFT.

Problem: otrzymujemy ciąg binarny So długości n i chcemy znaleźć w nim trzy równo rozmieszczone jedynki. Na przykład Smoże być 110110010, gdzie n = 9. Ma równomiernie rozmieszczone jedynki w pozycjach 2, 5 i 8.

1. Zeskanuj od Slewej do prawej i zrób listę Lpozycji o wartości 1. W S=110110010powyższym przykładzie mamy listę L = [1, 2, 4, 5, 8]. Ten krok to O (n). Problemem jest znalezienie arytmetyczny długości 3 w L, to znaczy wyraźne znalezienie A, B i C, w Ltaki że ba = CB lub równoważnie a + c = 2b . W powyższym przykładzie chcemy znaleźć progresję (2, 5, 8).

2. Utwórz wielomian p z wyrazami x ^k dla każdego k in L. W powyższym przykładzie tworzymy wielomian p (x) = (x + x ² + x ⁴ + x ⁵ + x ⁸ ) . Ten krok to O (n).

3. Znajdź wielomian q= p ² , używając szybkiej transformaty Fouriera . W powyższym przykładzie otrzymujemy wielomian q (x) = x ¹⁶ + 2x ¹³ + 2x ¹² + 3x ¹⁰ + 4x ⁹ + x ⁸ + 2x ⁷ + 4x ⁶ + 2x ⁵ + x ⁴ + 2x ³ + x ² . Ten krok to O (n log n).

4. Zignoruj ​​wszystkie terminy z wyjątkiem tych odpowiadających x ^2k dla niektórych k in L. W powyższym przykładzie otrzymujemy wyrazy x ¹⁶ , 3x ¹⁰ , x ⁸ , x ⁴ , x ² . Ten krok jest O (n), jeśli w ogóle zdecydujesz się to zrobić.

Oto kluczowy punkt: współczynnik dowolnego x ^2b dla b in Ljest dokładnie liczba par (a, c) na Ltak że a + c = 2b . [CLRS, przykł. 30.1-7] Jedna taka para to (b, b) zawsze (więc współczynnik wynosi co najmniej 1), ale jeśli istnieje jakaś inna para (a, c) , to współczynnik wynosi co najmniej 3, z (a, c ) i (c, a) . W powyższym przykładzie współczynnik x ¹⁰ wynosi 3 dokładnie ze względu na AP (2,5,8). (Współczynniki te x ^2bz powyższych powodów zawsze będą liczbami nieparzystymi. A wszystkie inne współczynniki w q zawsze będą parzyste).

Zatem algorytm polega na sprawdzeniu współczynników tych terminów x ^2b i sprawdzeniu, czy któryś z nich jest większy niż 1. Jeśli nie ma żadnego, to nie ma równych odstępów 1s. Jeśli nie jest b , w Lodniesieniu do których współczynnik x ^2b jest większy niż 1, to wiemy, że pewne pary (A, C) - inny niż (B, B) - dla których a + c = 2b . Aby znaleźć rzeczywistą parę, po prostu wypróbowujemy każdą a in L(odpowiadające c byłoby 2b-a ) i sprawdzamy, czy jest 1 na pozycji 2b-a in S. Ten krok to O (n).

To wszystko, ludzie.

Ktoś mógłby zapytać: czy musimy używać FFT? Wiele odpowiedzi, takich jak beta , flybywire i rsp , sugeruje, że podejście, które sprawdza każdą parę jedynek i sprawdza, czy jest 1 na „trzeciej” pozycji, może działać w O (n log n), w oparciu o intuicję że jeśli jest zbyt wiele jedynek, łatwo znaleźlibyśmy potrójną, a jeśli jest za mało jedynek, sprawdzenie wszystkich par zajmuje mało czasu. Niestety, chociaż ta intuicja jest słuszna, a proste podejście jest lepsze niż O (n ² ), nie jest znacznie lepsze. Podobnie jak w odpowiedzi sdcvvc , możemy wziąć „zbiór podobny do Cantora” ciągów o długości n = 3 ^k , z 1 na pozycjach, których trójskładnikowa reprezentacja zawiera tylko 0 i 2 (bez 1). Taki ciąg ma 2 ^k = n ^{(log 2) / (log 3)} ≈ n ^0,63 jedynek i nie ma równych 1s, więc sprawdzenie wszystkich par byłoby rzędu kwadratu liczby jedynek w nim: 4 ^k ≈ n ^1,26, co niestety jest asymptotycznie dużo większe niż (n log n). W rzeczywistości najgorszy przypadek jest jeszcze gorszy: Leo Moser w 1953 roku skonstruował (skutecznie) takie struny, które mają n ^{1-c / √ (log n)} 1s w sobie, ale nie są równo rozstawione 1s, co oznacza, że ​​na takich strunach proste podejście wymagałoby Θ (n ^{2-2c / √ (log n)} )- tylko maleńki nieco lepiej niż Θ (n = ² ) , o dziwo!

Około maksymalnej liczby jedynek w ciągu o długości n bez 3 równomiernie rozmieszczonych (co widzieliśmy powyżej było co najmniej n ^0,63 z łatwej konstrukcji podobnej do Cantora, a co najmniej n ^{1-c / √ (log n)} z Mosera) - to OEIS A003002 . Można ją również obliczyć bezpośrednio z OEIS A065825 jako k tak, że A065825 (k) ≤ n <A065825 (k + 1). Napisałem program, żeby je znaleźć i okazuje się, że chciwy algorytm nie podaje najdłuższego takiego ciągu. Na przykład dla n = 9 możemy otrzymać 5 1s (110100011), ale chciwy daje tylko 4 (110110000), dla n = 26 możemy otrzymać 11 1s (11001010001000010110001101) ale chciwy daje tylko 8 (11011000011011000000000000), a za n = 74 możemy dostać 22 1s (1100001011000100000101101000100000000000000001000101101000001000110100000000) n = 74 możemy dostać 22 1s (1100001011000100000101101000100000000000000001000101101000001000110100000000) n = 74001100 Zgadzają się jednak w kilku miejscach do 50 (np. We wszystkich 38 do 50). Jak mówią referencje OEIS, wydaje się, że Jarosław Wróblewski jest zainteresowany tą kwestią i prowadzi stronę internetową na tych nieśrednianych zbiorach . Dokładne liczby znane są tylko do 194.

W artykule (1999) twój problem nazywa się ŚREDNIA :

Problem jest 3SUM-trudny, jeśli występuje subkwadratowa redukcja z problemu 3SUMA: Czy mając zbiór A n liczb całkowitych, istnieją elementy a, b, c w A takie, że a + b + c = 0? Nie wiadomo, czy AVERAGE jest 3SUM-trudne. Istnieje jednak prosta liniowa redukcja w czasie od ŚREDNIA do 3SUM, której opis pomijamy.

Wikipedia :

Gdy liczby całkowite mieszczą się w zakresie [−u ... u], 3SUM można rozwiązać w czasie O (n + u lg u), przedstawiając S jako wektor bitowy i wykonując splot przy użyciu FFT.

To wystarczy, aby rozwiązać Twój problem :).

Co jest bardzo ważne jest to, że O (n log n) jest złożony w kategoriach liczby zer i jedynek, a nie liczba jedynek (który może być podawany w postaci tablicy, jak [1,5,9,15]). Sprawdzenie, czy zbiór ma ciąg arytmetyczny, wyrażony w liczbie jedynek, jest trudne i zgodnie z tym artykułem od 1999 roku nie jest znany algorytm szybszy niż O (n ² ) i przypuszcza się, że nie istnieje. Każdy, kto tego nie bierze pod uwagę, próbuje rozwiązać otwarty problem.

Inne interesujące informacje, przeważnie niecodzienne:

Dolna granica:

Łatwą dolną granicą jest zbiór podobny do Cantora (liczby 1..3 ^ n-1 niezawierające 1 w swojej potrójnej rozwinięciu) - jego gęstość wynosi n ^ (log_3 2) (około 0,631). Zatem każde sprawdzenie, czy zbiór nie jest zbyt duży, a następnie sprawdzenie wszystkich par nie wystarczy, aby uzyskać O (n log n). Musisz mądrzej zbadać sekwencję. Cytujemy tutaj lepszą dolną granicę - to n ^{1-c / (log (n)) ^ (1/2)} . Oznacza to, że zestaw Cantora nie jest optymalny.

Górna granica - mój stary algorytm:

Wiadomo, że dla dużego n podzbiór {1, 2, ..., n} nie zawierający progresji arytmetycznej ma co najwyżej n / (log n) ^ (1/20) elementów. Artykuł O trójek w ciągu arytmetycznym dowodzi więcej: zbiór nie może zawierać więcej niż n * 2 ²⁸ * (log log n / log n) ^1/2 elementów. Możesz więc sprawdzić, czy ta granica jest osiągnięta, a jeśli nie, naiwnie sprawdzić pary. Jest to algorytm O (n ² * log log n / log n), szybszy niż O (n ² ). Niestety „O trójek…” jest na Springer - ale pierwsza strona jest dostępna, a ekspozycja Bena Greena jest dostępna tutaj , strona 28, twierdzenie 24.

Nawiasem mówiąc, prace pochodzą z 1999 roku - tego samego roku, co pierwszy, o którym wspomniałem, więc pewnie dlatego ten pierwszy nie wspomina o tym wyniku.

To nie jest rozwiązanie, ale sposób myślenia podobny do tego, co myślał Olexiy

Bawiłem się tworzeniem sekwencji z maksymalną liczbą jedynek i wszystkie są dość interesujące, mam do 125 cyfr, a oto pierwsze 3 liczby, które znalazłem, próbując wstawić jak najwięcej bitów „1”:

• 1101100001101100000000000000110110000110110000000000000000000000000000000000000001101100001101100000000000011011000011011
• 101101000101101000000000000101101000101101000000000000000000000000000000000000000101101000101101000000000000101101000101101
• 100110010100110010000000000100110010100110010000000000000000000000000000000000010011001010011001000000000010011001010011001

Zauważ, że wszystkie są fraktalami (nie jest to zbyt zaskakujące, biorąc pod uwagę ograniczenia). Być może jest coś w myśleniu wstecz, być może jeśli struna nie jest fraktalem o charakterystyce, to musi mieć powtarzający się wzór?

Dzięki beta za lepsze określenie tych liczb.

Aktualizacja: Niestety, wygląda na to, że wzór nie działa, gdy zaczyna się od wystarczająco dużego ciągu początkowego, takiego jak: 10000000000001:

100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001

Podejrzewam, że proste podejście, które wygląda jak O (n ^ 2), faktycznie da coś lepszego, jak O (n ln (n)). Sekwencje, których testowanie trwa najdłużej (dla danego n), to te, które nie zawierają trio, co nakłada poważne ograniczenia na liczbę jedynek, które mogą występować w sekwencji.

Wymyśliłem kilka argumentów machających rękami, ale nie udało mi się znaleźć porządnego dowodu. Zamierzam zaryzykować: odpowiedzią jest bardzo sprytny pomysł, o którym profesor wiedział od tak dawna, że ​​wydaje się to oczywiste, ale dla uczniów jest to zbyt trudne. (Albo to, albo przespałeś wykład, który to dotyczył).

Aktualizacja: 2009-10-17 23:00

Uruchomiłem to na dużych liczbach (na przykład ciągach 20 milionów) i teraz uważam, że ten algorytm nie jest O (n logn). Mimo to jest to wystarczająco fajna implementacja i zawiera szereg optymalizacji, dzięki którym działa naprawdę szybko. Ocenia wszystkie układy ciągów binarnych 24 lub mniej cyfr w mniej niż 25 sekund.

Zaktualizowałem kod, aby uwzględnić 0 <= L < M < U <= X-1obserwację z dzisiejszego dnia.

Oryginalny

Jest to koncepcja podobna do innego pytania, na które odpowiedziałem . Ten kod sprawdził również trzy wartości w serii i określił, czy trójka spełnia warunek. Oto kod C # dostosowany z tego:

using System;
using System.Collections.Generic;

namespace StackOverflow1560523
{
    class Program
    {
        public struct Pair<T>
        {
            public T Low, High;
        }
        static bool FindCandidate(int candidate, 
            List<int> arr, 
            List<int> pool, 
            Pair<int> pair, 
            ref int iterations)
        {
            int lower = pair.Low, upper = pair.High;
            while ((lower >= 0) && (upper < pool.Count))
            {
                int lowRange = candidate - arr[pool[lower]];
                int highRange = arr[pool[upper]] - candidate;
                iterations++;
                if (lowRange < highRange)
                    lower -= 1;
                else if (lowRange > highRange)
                    upper += 1;
                else
                    return true;
            }
            return false;
        }
        static List<int> BuildOnesArray(string s)
        {
            List<int> arr = new List<int>();
            for (int i = 0; i < s.Length; i++)
                if (s[i] == '1')
                    arr.Add(i);
            return arr;
        }
        static void BuildIndexes(List<int> arr, 
            ref List<int> even, ref List<int> odd, 
            ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
        {
            for (int i = 0; i < arr.Count; i++)
            {
                bool isEven = (arr[i] & 1) == 0;
                if (isEven)
                {
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
                    even.Add(i);
                }
                else
                {
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
                    odd.Add(i);
                }
            }
        }

        static int FindSpacedOnes(string s)
        {
            // List of indexes of 1s in the string
            List<int> arr = BuildOnesArray(s);
            //if (s.Length < 3)
            //    return 0;

            //  List of indexes to odd indexes in arr
            List<int> odd = new List<int>(), even = new List<int>();

            //  evenIndex has indexes into arr to bracket even numbers
            //  oddIndex has indexes into arr to bracket odd numbers
            List<Pair<int>> evenIndex = new List<Pair<int>>(), 
                oddIndex = new List<Pair<int>>(); 
            BuildIndexes(arr, 
                ref even, ref odd, 
                ref evenIndex, ref oddIndex);

            int iterations = 0;
            for (int i = 1; i < arr.Count-1; i++)
            {
                int target = arr[i];
                bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) || 
                    FindCandidate(target, arr, even, evenIndex[i], ref iterations);
                if (found)
                    return iterations;
            }
            return iterations;
        }
        static IEnumerable<string> PowerSet(int n)
        {
            for (long i = (1L << (n-1)); i < (1L << n); i++)
            {
                yield return Convert.ToString(i, 2).PadLeft(n, '0');
            }
        }
        static void Main(string[] args)
        {
            for (int i = 5; i < 64; i++)
            {
                int c = 0;
                string hardest_string = "";
                foreach (string s in PowerSet(i))
                {
                    int cost = find_spaced_ones(s);
                    if (cost > c)
                    {
                        hardest_string = s;
                        c = cost;
                        Console.Write("{0} {1} {2}\r", i, c, hardest_string);
                    }
                }
                Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
            }
        }
    }
}

Główne różnice to:

1. Wyczerpujące wyszukiwanie rozwiązań
   Ten kod generuje zestaw danych umożliwiających znalezienie najtrudniejszych danych wejściowych do rozwiązania dla tego algorytmu.
2. Wszystkie rozwiązania a najtrudniejsze do rozwiązania
   Kod poprzedniego pytania wygenerował wszystkie rozwiązania za pomocą generatora Pythona. Ten kod wyświetla tylko najtrudniejsze dla każdej długości wzoru.
3. Algorytm oceniania
   Ten kod sprawdza odległość od środkowego elementu do jego lewej i prawej krawędzi. Kod Pythona sprawdzał, czy suma była powyżej czy poniżej 0.
4. Zbieżność na kandydacie
   Bieżący kod działa od środka do krawędzi, aby znaleźć kandydata. Kod w poprzednim zadaniu działał od krawędzi do środka. Ta ostatnia zmiana daje dużą poprawę wydajności.
5. Użycie pul parzystych i nieparzystych
   Na podstawie obserwacji pod koniec tego zapisu, kod przeszukuje pary parzystych liczb par liczb nieparzystych, aby znaleźć L i U, utrzymując M na stałym poziomie. Zmniejsza to liczbę wyszukiwań poprzez wstępne obliczenie informacji. W związku z tym kod wykorzystuje dwa poziomy pośrednictwa w głównej pętli FindCandidate i wymaga dwóch wywołań FindCandidate dla każdego środkowego elementu: raz dla liczb parzystych i raz dla nieparzystych.

Ogólną ideą jest praca na indeksach, a nie na surowej reprezentacji danych. Obliczenie tablicy, w której pojawiają się jedynki, pozwala algorytmowi działać w czasie proporcjonalnym do liczby jedynek w danych, a nie w czasie proporcjonalnym do długości danych. To jest standardowa transformacja: stwórz strukturę danych, która pozwoli na szybsze działanie przy zachowaniu równoważności problemu.

Wyniki są nieaktualne: usunięte.

Edycja: 16.10.2009 18:48

Na danych yx, którym da się wiarę w inne odpowiedzi, jako reprezentatywne dla danych trudnych do obliczenia, otrzymuję te wyniki ... Usunąłem je. Są nieaktualne.

Chciałbym zwrócić uwagę, że te dane nie są najtrudniejsze dla mojego algorytmu, więc myślę, że założenie, że fraktale yx są najtrudniejsze do rozwiązania, jest błędne. Spodziewam się, że najgorszy przypadek dla określonego algorytmu będzie zależał od samego algorytmu i prawdopodobnie nie będzie spójny w różnych algorytmach.

Edycja: 2009-10-17 13:30

Dalsze obserwacje na ten temat.

Najpierw przekonwertuj ciąg zer i jedynek na tablicę indeksów dla każdej pozycji jedynek. Powiedzmy, że długość tej tablicy A wynosi X. Wtedy celem jest znalezienie

0 <= L < M < U <= X-1

takie że

A[M] - A[L] = A[U] - A[M]

lub

2*A[M] = A[L] + A[U]

Ponieważ A [L] i A [U] sumują się do liczby parzystej, nie mogą być (parzyste, nieparzyste) ani (nieparzyste, parzyste). Wyszukiwanie dopasowania można ulepszyć, dzieląc A [] na pule nieparzyste i parzyste i wyszukując dopasowania na A [M] w pulach kandydatów nieparzystych i parzystych po kolei.

Myślę jednak, że jest to bardziej optymalizacja wydajności niż ulepszenie algorytmiczne. Liczba porównań powinna spaść, ale kolejność algorytmu powinna być taka sama.

Edytuj 2009-10-18 00:45

Przychodzi mi do głowy jeszcze inna optymalizacja, w tym samym duchu, co rozdzielenie kandydatów na parzyste i nieparzyste. Ponieważ trzy indeksy muszą dodać się do wielokrotności 3 (a, a + x, a + 2x - mod 3 wynosi 0, niezależnie od a i x), można oddzielić L, M i U do ich wartości mod 3 :

M  L  U
0  0  0
   1  2
   2  1
1  0  2
   1  1
   2  0
2  0  1
   1  0
   2  2

W rzeczywistości możesz połączyć to z obserwacją parzystych / nieparzystych i podzielić je na ich wartości mod 6:

M  L  U
0  0  0
   1  5
   2  4
   3  3
   4  2
   5  1

i tak dalej. Zapewniłoby to dalszą optymalizację wydajności, ale nie przyspieszyłoby algorytmiczne.

Nie udało mi się jeszcze znaleźć rozwiązania :(, ale mam kilka pomysłów.

A co jeśli zaczniemy od odwrotnego problemu: skonstruuj sekwencję z maksymalną liczbą jedynek i BEZ równo rozmieszczonych trio. Jeśli możesz udowodnić, że maksymalna liczba jedynek wynosi o (n), możesz poprawić swoje oszacowanie, powtarzając tylko listę jedynek.

To może pomóc ...

Ten problem sprowadza się do następujących kwestii:

Mając sekwencję dodatnich liczb całkowitych, znajdź ciągły podciąg podzielony na przedrostek i sufiks w taki sposób, aby suma przedrostka podciągów była równa sumie sufiksu podciągów.

Na przykład, mając sekwencję of [ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ], znaleźlibyśmy podciąg [ 3, 6, 5, 2, 2]z przedrostkiem [ 3, 6 ]z sumą przedrostka 9i sufiksem [ 5, 2, 2 ]z sumą sufiksów of 9.

Redukcja jest następująca:

Biorąc pod uwagę sekwencję zer i jedynek i zaczynając od pierwszego z lewej, kontynuuj przesuwanie w prawo. Za każdym razem, gdy napotkasz kolejny, zapisz liczbę ruchów od napotkania poprzedniego i dołącz tę liczbę do wynikowej sekwencji.

Na przykład, biorąc pod uwagę sekwencję [ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ], znaleźlibyśmy redukcję [ 1, 3, 4]. Na podstawie tej redukcji obliczamy ciągły podciąg z [ 1, 3, 4], przedrostek [ 1, 3]z sumą 4i przyrostek [ 4 ]z sumą 4.

Zmniejszenie to można obliczyć w O(n).

Niestety nie jestem pewien, dokąd się stąd udać.

Dla prostego typu problemu (tj. Wyszukujesz trzy „1” z tylko (tj. Zerem lub więcej) „0” między nimi), jest to całkiem proste: możesz po prostu podzielić sekwencję na każde „1” i poszukać dwóch sąsiednich podciągów mających tej samej długości (oczywiście drugi podciąg nie jest ostatnim). Oczywiście można to zrobić w czasie O (n) .

W przypadku bardziej złożonej wersji (tj. Przeszukujesz indeks i i lukę g > 0 taką, że s[i]==s[i+g]==s[i+2*g]=="1"), nie jestem pewien, czy istnieje rozwiązanie O (n log n) , ponieważ prawdopodobnie istnieje O (n²) trioli mających ta właściwość (pomyśl o ciągu wszystkich jedynek, takich trojaczków jest około n² / 2 ). Oczywiście szukasz tylko jednego z nich, ale obecnie nie mam pomysłu, jak go znaleźć ...

Zabawne pytanie, ale kiedy zdasz sobie sprawę, że rzeczywisty wzorzec między dwoma „jedynkami” nie ma znaczenia, algorytm wygląda tak:

• skanowanie, poszukaj '1'
• zaczynając od następnego skanowania pozycji w poszukiwaniu kolejnej „1” (do końca tablicy minus odległość od bieżącej pierwszej „1” lub w przeciwnym razie trzecia „1” byłaby poza zakresem)
• jeśli na pozycji drugiej „1” plus odległość do pierwszej 1 „zostanie znaleziona trzecia„ 1 ”, mamy równe odstępy.

W kodzie, w stylu JTest (zauważ, że ten kod nie jest napisany jako najbardziej wydajny i dodałem kilka println, aby zobaczyć, co się stanie).

import java.util.Random;

import junit.framework.TestCase;

public class AlgorithmTest extends TestCase {

 /**
  * Constructor for GetNumberTest.
  *
  * @param name The test's name.
  */
 public AlgorithmTest(String name) {
  super(name);
 }

 /**
  * @see TestCase#setUp()
  */
 protected void setUp() throws Exception {
  super.setUp();
 }

 /**
  * @see TestCase#tearDown()
  */
 protected void tearDown() throws Exception {
  super.tearDown();
 }

 /**
  * Tests the algorithm.
  */
 public void testEvenlySpacedOnes() {

  assertFalse(isEvenlySpaced(1));
  assertFalse(isEvenlySpaced(0x058003));
  assertTrue(isEvenlySpaced(0x07001));
  assertTrue(isEvenlySpaced(0x01007));
  assertTrue(isEvenlySpaced(0x101010));

  // some fun tests
  Random random = new Random();

  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
  isEvenlySpaced(random.nextLong());
 }

 /**
  * @param testBits
  */
 private boolean isEvenlySpaced(long testBits) {
  String testString = Long.toBinaryString(testBits);
  char[] ones = testString.toCharArray();
  final char ONE = '1';

  for (int n = 0; n < ones.length - 1; n++) {

   if (ONE == ones[n]) {
    for (int m = n + 1; m < ones.length - m + n; m++) {

     if (ONE == ones[m] && ONE == ones[m + m - n]) {
      System.out.println(" IS evenly spaced: " + testBits + '=' + testString);
      System.out.println("               at: " + n + ", " + m + ", " + (m + m - n));
      return true;
     }
    }
   }
  }

  System.out.println("NOT evenly spaced: " + testBits + '=' + testString);
  return false;
 }
}

Pomyślałem o podejściu dziel i rządź, które mogłoby się sprawdzić.

Po pierwsze, w przetwarzaniu wstępnym musisz wstawić wszystkie liczby mniejsze niż połowa rozmiaru wejściowego ( n / 3) do listy.

Biorąc pod uwagę ciąg: 0000010101000100(zwróć uwagę, że ten konkretny przykład jest prawidłowy)

Wstaw wszystkie liczby pierwsze (i 1) od 1 do (16/2) do listy: {1, 2, 3, 4, 5, 6, 7}

Następnie podziel go na pół:

100000101 01000100

Rób to, aż dojdziesz do łańcuchów o rozmiarze 1. Dla wszystkich łańcuchów o rozmiarze jeden, które zawierają 1, dodaj indeks ciągu do listy możliwości; w przeciwnym razie zwraca -1 w przypadku niepowodzenia.

Musisz także zwrócić listę wciąż możliwych odległości odstępów, powiązanych z każdym indeksem początkowym. (Zacznij od listy, którą utworzyłeś powyżej i usuwaj liczby na bieżąco) W tym przypadku pusta lista oznacza, że ​​masz do czynienia tylko z jedną 1, więc w tym momencie możliwe są dowolne odstępy; w przeciwnym razie lista zawiera odstępy, które należy wykluczyć.

Kontynuując powyższy przykład:

1000 0101 0100 0100

10 00 01 01 01 00 01 00

1 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0

W pierwszym etapie łączenia mamy teraz osiem zestawów po dwa. W pierwszym mamy możliwość zbioru, ale dowiadujemy się, że odstęp o 1 jest niemożliwy, ponieważ jest tam drugie zero. Więc zwracamy 0 (dla indeksu) i {2,3,4,5,7} dla faktu, że odstępy o 1 są niemożliwe. W drugim nie mamy nic, więc zwracamy -1. W trzecim mamy dopasowanie bez usuniętych odstępów w indeksie 5, więc zwraca 5, {1,2,3,4,5,7}. W czwartej parze zwracamy 7, {1,2,3,4,5,7}. W piątym zwróć 9, {1, 2, 3, 4, 5, 7}. W szóstym zwróć -1. W siódmym zwróć 13, {1, 2, 3, 4, 5, 7}. W ósmym zwróć -1.

Łącząc ponownie w cztery zestawy po cztery, mamy:

1000: Return (0, {4,5,6,7}) 0101: Return (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6 , 7}) 0100: Return (9, {3,4,5,6,7}) 0100: Return (13, {3,4,5,6,7})

Łączenie w zestawy po osiem:

10000101: Return (0, {5,7}), (5, {2,3,4,5,6,7}), (7, {1,2,3,4,5,6,7}) 01000100: Zwrot (9, {4,7}), (13, {3,4,5,6,7})

Łączenie w zestaw szesnastu:

10000101 01000100

W miarę postępów sprawdzamy wszystkie dotychczasowe możliwości. Aż do tego kroku zostawialiśmy rzeczy, które wykraczały poza koniec łańcucha, ale teraz możemy sprawdzić wszystkie możliwości.

Zasadniczo sprawdzamy pierwszą 1 z odstępami 5 i 7 i stwierdzamy, że nie pokrywają się one z 1. (Zwróć uwagę, że każdy test jest STAŁY, a nie jest czasem liniowym) Następnie sprawdzamy drugi (indeks 5) z odstępami 2, 3, 4, 5, 6 i 7 - lub moglibyśmy, ale możemy zatrzymać się na 2, ponieważ to faktycznie pasuje.

Uff! To dość długi algorytm.

Nie wiem w 100%, czy to O (n log n) z powodu ostatniego kroku, ale wszystko, co tam jest, jest zdecydowanie O (n log n), o ile wiem. Wrócę do tego później i spróbuję udoskonalić ostatni krok.

EDYCJA: Zmieniłem moją odpowiedź, aby odzwierciedlić komentarz Welboga. Przepraszamy za błąd. Pseudokod napiszę później, gdy będę miał trochę więcej czasu na rozszyfrowanie tego, co napisałem ponownie. ;-)

Podam tutaj moje przybliżone przypuszczenie i pozwolę tym, którzy są lepsi w obliczaniu złożoności, aby pomogli mi w tym, jak mój algorytm radzi sobie w notacji O

1. podany ciąg binarny 0000010101000100 (jako przykład)
2. przyciąć głowę i koniec zer -> 00000 101010001 00
3. otrzymujemy 101010001 z poprzednich obliczeń
4. sprawdź, czy środkowy bit to `` jeden '', jeśli prawda, znaleziono prawidłowe trzy równomiernie rozmieszczone `` jedynki '' (tylko jeśli liczba bitów jest nieparzysta)
5. odpowiednio, jeśli pozostała przycięta liczba bitów jest parzysta, część „jedynki” z głowy i ogona nie może być częścią równo rozmieszczonego „jedynki”,
6. używamy 1010100001 jako przykładu (z dodatkowym „zerem”, aby uzyskać parzyste przycięcie), w tym przypadku musimy ponownie przyciąć, a następnie staje się -> 10101 00001
7. otrzymujemy 10101 z poprzednich obliczeń i sprawdzamy środkowy bit i ponownie znaleźliśmy równo rozmieszczony bit

Nie mam pojęcia, jak obliczyć złożoność tego, czy ktoś może pomóc?

edycja: dodaj kod ilustrujący mój pomysł

edit2: próbowałem skompilować mój kod i znalazłem kilka poważnych błędów, naprawiono

char *binaryStr = "0000010101000100";

int main() {
   int head, tail, pos;
   head = 0;
   tail = strlen(binaryStr)-1;
   if( (pos = find3even(head, tail)) >=0 )
      printf("found it at position %d\n", pos);
   return 0;
}

int find3even(int head, int tail) {
   int pos = 0;
   if(head >= tail) return -1;
   while(binaryStr[head] == '0') 
      if(head<tail) head++;
   while(binaryStr[tail] == '0') 
      if(head<tail) tail--;
   if(head >= tail) return -1;
   if( (tail-head)%2 == 0 && //true if odd numbered
       (binaryStr[head + (tail-head)/2] == '1') ) { 
         return head;
   }else {
      if( (pos = find3even(head, tail-1)) >=0 )
         return pos;
      if( (pos = find3even(head+1, tail)) >=0 )
         return pos;
   }
   return -1;
}

Wymyśliłem coś takiego:

def IsSymetric(number):
    number = number.strip('0')

    if len(number) < 3:
        return False
    if len(number) % 2 == 0:
        return IsSymetric(number[1:]) or IsSymetric(number[0:len(number)-2])
    else:
        if number[len(number)//2] == '1':
            return True
        return IsSymetric(number[:(len(number)//2)]) or IsSymetric(number[len(number)//2+1:])
    return False

Inspiruje to andycjw.

1. Obetnij zera.
2. Jeśli nawet wtedy przetestuj dwa podciągi 0 - (len-2) (pomiń ostatni znak) i od 1 - (len-1) (pomiń pierwszy znak)
3. Jeśli nawet, jeśli środkowy znak jest jeden, to mamy sukces. W przeciwnym razie podziel sznurek na środku bez elementu środkowego i sprawdź obie części.

Jeśli chodzi o złożoność, może to być O (nlogn), ponieważ w każdej rekursji dzielimy przez dwa.

Mam nadzieję, że to pomoże.

Ok, zamierzam ponownie zająć się problemem. Myślę, że mogę udowodnić algorytm O (n log (n)), który jest podobny do tych już omówionych, używając zbalansowanego drzewa binarnego do przechowywania odległości między 1. Podejście to zostało zainspirowane obserwacją Justice'a, że ​​problem sprowadza się do listy odległości między jedynkami.

Czy moglibyśmy przeskanować ciąg wejściowy, aby skonstruować zrównoważone drzewo binarne wokół pozycji 1, tak że każdy węzeł przechowuje pozycję 1, a każda krawędź jest oznaczona odległością do sąsiedniej 1 dla każdego węzła podrzędnego. Na przykład:

10010001 gives the following tree

      3
     / \
  2 /   \ 3
   /     \
  0       7

Można to zrobić w O (n log (n)), ponieważ dla łańcucha o rozmiarze n każde wstawienie przyjmuje O (log (n)) w najgorszym przypadku.

Następnie problem polega na przeszukaniu drzewa, aby odkryć, czy w jakimkolwiek węźle istnieje ścieżka od tego węzła do lewego dziecka, która ma taką samą odległość, jak ścieżka przez prawe dziecko. Można to zrobić rekurencyjnie na każdym poddrzewie. Łącząc dwa poddrzewa w wyszukiwaniu, musimy porównać odległości od ścieżek w lewym poddrzewie z odległościami od ścieżek w prawym. Ponieważ liczba ścieżek w poddrzewie będzie proporcjonalna do log (n), a liczba węzłów to n, uważam, że można to zrobić w czasie O (n log (n)).

Czy coś przegapiłem?

Wydawało się, że to fajny problem, więc postanowiłem spróbować swoich sił.

Zakładam, że 111000001 znajdzie pierwsze 3 i odniesie sukces. Zasadniczo liczba zer po 1 jest ważna, ponieważ 0111000 to to samo, co 111000 zgodnie z twoją definicją. Gdy znajdziesz dwa przypadki z 1, następny znaleziony 1 kończy trylogię.

Tutaj jest w Pythonie:

def find_three(bstring):
    print bstring
    dict = {}
    lastone = -1
    zerocount = 0
    for i in range(len(bstring)):
        if bstring[i] == '1':
            print i, ': 1'
            if lastone != -1:
                if(zerocount in dict):
                    dict[zerocount].append(lastone)
                    if len(dict[zerocount]) == 2:
                        dict[zerocount].append(i)
                        return True, dict
                else:
                    dict[zerocount] = [lastone]
            lastone = i
            zerocount = 0
        else:
            zerocount = zerocount + 1
    #this is really just book keeping, as we have failed at this point
    if lastone != -1:
        if(zerocount in dict):
            dict[zerocount].append(lastone)
        else:
            dict[zerocount] = [lastone]
    return False, dict

To jest pierwsza próba, więc jestem pewien, że można to napisać w bardziej przejrzysty sposób. Proszę wymienić poniżej przypadki, w których ta metoda zawodzi.

Zakładam, że powodem tego jest nlog (n) jest następujący:

• Aby znaleźć 1, która jest początkiem trójki, musisz sprawdzić (n-2) znaków. Jeśli nie znalazłeś tego do tego momentu, nie (znaki n-1 i n nie mogą rozpocząć trioli) (O (n))
• Aby znaleźć drugą 1, która jest częścią trioli (zaczynając od pierwszej), musisz sprawdzić m / 2 (m = nx, gdzie x jest przesunięciem pierwszych 1) znaków. Dzieje się tak, ponieważ jeśli nie znalazłeś drugiej 1 do czasu, gdy jesteś w połowie drogi od pierwszej do końca, nie znajdziesz ... ponieważ trzecia 1 musi znajdować się dokładnie w tej samej odległości od drugiej. (O (log (n)))
• To O (1), aby znaleźć ostatnią 1, ponieważ znasz indeks, w którym musi się znajdować, zanim znajdziesz pierwszą i drugą.

Więc masz n, log (n) i 1 ... O (nlogn)

Edycja: Ups, moja wina. Mój mózg ustawił, że n / 2 zostało zarejestrowane ... co oczywiście nie jest (podwojenie liczby pozycji nadal podwaja liczbę iteracji w pętli wewnętrznej). To wciąż jest n ^ 2, nie rozwiązując problemu. Cóż, przynajmniej muszę napisać jakiś kod :)

Wdrożenie w Tcl

proc get-triplet {input} {
    for {set first 0} {$first < [string length $input]-2} {incr first} {
        if {[string index $input $first] != 1} {
            continue
        }
        set start [expr {$first + 1}]
        set end [expr {1+ $first + (([string length $input] - $first) /2)}]
        for {set second $start} {$second < $end} {incr second} {
            if {[string index $input $second] != 1} {
                continue
            }
            set last [expr {($second - $first) + $second}]
            if {[string index $input $last] == 1} {
                return [list $first $second $last]
            }
        }
    }
    return {}
}

get-triplet 10101      ;# 0 2 4
get-triplet 10111      ;# 0 2 4
get-triplet 11100000   ;# 0 1 2
get-triplet 0100100100 ;# 1 4 7

Myślę, że znalazłem sposób na rozwiązanie problemu, ale nie mogę skonstruować formalnego dowodu. Rozwiązanie, które stworzyłem, jest napisane w Javie i używa licznika „n”, aby policzyć, ile list / tablic uzyskuje dostęp. Zatem n powinno być mniejsze lub równe stringLength * log (stringLength), jeśli jest poprawne. Wypróbowałem to dla liczb od 0 do 2 ^ 22 i działa.

Rozpoczyna się iteracją po ciągu wejściowym i utworzeniem listy wszystkich indeksów, które zawierają jedynkę. To jest po prostu O (n).

Następnie z listy indeksów wybiera firstIndex i secondIndex, który jest większy niż pierwszy. Te dwa indeksy muszą zawierać jedynki, ponieważ znajdują się na liście indeksów. Stamtąd można obliczyć thirdIndex. Jeśli inputString [thirdIndex] ma wartość 1, to zatrzymuje się.

public static int testString(String input){
//n is the number of array/list accesses in the algorithm
int n=0;

//Put the indices of all the ones into a list, O(n)
ArrayList<Integer> ones = new ArrayList<Integer>();
for(int i=0;i<input.length();i++){
    if(input.charAt(i)=='1'){
        ones.add(i);
    }
}

//If less than three ones in list, just stop
if(ones.size()<3){
    return n;
}

int firstIndex, secondIndex, thirdIndex;
for(int x=0;x<ones.size()-2;x++){
    n++;
    firstIndex = ones.get(x);

    for(int y=x+1; y<ones.size()-1; y++){
        n++;
        secondIndex = ones.get(y);
        thirdIndex = secondIndex*2 - firstIndex;

        if(thirdIndex >= input.length()){
            break;
        }

        n++;
        if(input.charAt(thirdIndex) == '1'){
            //This case is satisfied if it has found three evenly spaced ones
            //System.out.println("This one => " + input);
            return n;
        }
    }
}

return n;

}

uwaga dodatkowa: licznik n nie jest zwiększany, gdy iteruje po ciągu wejściowym w celu skonstruowania listy indeksów. Ta operacja to O (n), więc i tak nie będzie miała wpływu na złożoność algorytmu.

Jednym z wejść w problem jest myślenie o czynnikach i zmianach.

Dzięki przesunięciu porównujesz ciąg jedynek i zer z przesuniętą wersją samego siebie. Następnie bierzesz pasujące. Weź ten przykład przesunięty o dwa:

1010101010
  1010101010
------------
001010101000

Wynikowe jedynki (bitowe i połączone operatorem logicznym) muszą reprezentować wszystkie jedynki, które są równo rozdzielone przez dwa. Ten sam przykład przesunięty o trzy:

1010101010
   1010101010
-------------
0000000000000

W tym przypadku nie ma 1, które są równomiernie oddalone od siebie o trzy.

Więc co ci to mówi? Cóż, wystarczy przetestować przesunięcia, które są liczbami pierwszymi. Na przykład, powiedzmy, że masz dwie jedynki, które różnią się od siebie o sześć. Musiałbyś przetestować tylko „dwie” zmiany i „trzy” zmiany (ponieważ dzielą one sześć). Na przykład:

10000010 
  10000010 (Shift by two)
    10000010
      10000010 (We have a match)

10000010
   10000010 (Shift by three)
      10000010 (We have a match)

Zatem jedyne przesunięcia, jakie kiedykolwiek musisz sprawdzić, to 2,3,5,7,11,13 itd. Aż do liczby pierwszej najbliższej pierwiastkowi kwadratowemu z rozmiaru ciągu cyfr.

Prawie rozwiązany?

Myślę, że jestem bliżej rozwiązania. Gruntownie:

1. Przeskanuj ciąg w poszukiwaniu 1. Na każdą 1 nutę to reszta po uwzględnieniu modułu jej pozycji. Moduł waha się od 1 do połowy rozmiaru struny. Dzieje się tak, ponieważ największy możliwy rozmiar separacji to połowa łańcucha. Odbywa się to w O (n ^ 2). ALE. Należy sprawdzić tylko moduły główne, więc O (n ^ 2 / log (n))
2. Sortuj listę modułów / reszt w kolejności od największego modułu, można to zrobić w czasie O (n * log (n)).
3. Poszukaj trzech kolejnych modułów / reszty, które są takie same.
4. Jakoś odzyskać pozycję tych!

Myślę, że największą wskazówką do odpowiedzi jest to, że najszybszymi algorytmami sortowania są O (n * log (n)).

ŹLE

Krok 1 jest błędny, jak wskazał kolega. Gdybyśmy mieli jedynki w pozycji 2,12 i 102. Wtedy przyjmując moduł 10, wszystkie miałyby te same reszty, ale nie byłyby jednakowo oddalone od siebie! Przepraszam.

Oto kilka myśli, które mimo moich najlepszych starań nie wydają się zawijać w łuk. Mimo to mogą być przydatnym punktem wyjścia do czyjejś analizy.

Rozważ zaproponowane rozwiązanie w następujący sposób, które jest podejściem, które sugerowało kilka osób, w tym ja we wcześniejszej wersji tej odpowiedzi. :)

1. Przytnij wiodące i końcowe zera.
2. Przeskanuj ciąg w poszukiwaniu jedynek.
3. Gdy zostanie znaleziona 1:
   1. Załóżmy, że jest to środkowe 1 rozwiązania.
   2. Dla każdej poprzedniej 1 użyj jej zapisanej pozycji do obliczenia przewidywanej pozycji ostatniej 1.
   3. Jeśli obliczona pozycja znajduje się po końcu ciągu, nie może być częścią rozwiązania, więc usuń pozycję z listy kandydatów.
   4. Sprawdź rozwiązanie.
4. Jeśli nie znaleziono rozwiązania, dodaj bieżącą 1 do listy kandydatów.
5. Powtarzaj, dopóki nie zostaną znalezione więcej 1.

Teraz rozważ ciągi wejściowe, takie jak następujące, które nie będą miały rozwiązania:

101
101001
1010010001
101001000100001
101001000100001000001

Ogólnie jest to konkatenacja k ciągów w postaci j 0, po której następuje 1 dla j od zera do k-1.

k=2  101
k=3  101001
k=4  1010010001
k=5  101001000100001
k=6  101001000100001000001

Zauważ, że długości podciągów wynoszą 1, 2, 3 itd. Zatem problem z rozmiarem n ma podciągi o długościach od 1 do k takie, że n = k (k + 1) / 2.

k=2  n= 3  101
k=3  n= 6  101001
k=4  n=10  1010010001
k=5  n=15  101001000100001
k=6  n=21  101001000100001000001

Zauważ, że k śledzi również liczbę jedynek, które musimy wziąć pod uwagę. Pamiętaj, że za każdym razem, gdy widzimy 1, musimy wziąć pod uwagę wszystkie 1 widziane do tej pory. Więc kiedy widzimy drugie 1, rozważamy tylko pierwsze, kiedy widzimy trzecie 1, rozważamy ponownie pierwsze dwa, kiedy widzimy czwartą 1, musimy ponownie rozważyć pierwsze trzy i tak dalej. Pod koniec algorytmu uwzględniliśmy k (k-1) / 2 par jedynek. Nazwij to p.

k=2  n= 3  p= 1  101
k=3  n= 6  p= 3  101001
k=4  n=10  p= 6  1010010001
k=5  n=15  p=10  101001000100001
k=6  n=21  p=15  101001000100001000001

Zależność między n i p jest taka, że ​​n = p + k.

Proces przechodzenia przez strunę zajmuje O (n) czasu. Za każdym razem, gdy napotkano 1, wykonywanych jest maksymalnie (k-1) porównań. Ponieważ n = k (k + 1) / 2, n> k ** 2, więc sqrt (n)> k. To daje nam O (n sqrt (n)) lub O (n ** 3/2). Zauważ jednak, że może to nie być naprawdę ścisłe ograniczenie, ponieważ liczba porównań waha się od 1 do maksimum k, przez cały czas nie jest to k. Ale nie jestem pewien, jak to wyjaśnić w matematyce.

To nadal nie jest O (n log (n)). Nie mogę też udowodnić, że te dane wejściowe są najgorszymi przypadkami, chociaż podejrzewam, że tak. Myślę, że gęstsze upakowanie 1 z przodu skutkuje jeszcze rzadszym upakowaniem na końcu.

Ponieważ ktoś może nadal uznać to za przydatne, oto mój kod dla tego rozwiązania w Perlu:

#!/usr/bin/perl

# read input as first argument
my $s = $ARGV[0];

# validate the input
$s =~ /^[01]+$/ or die "invalid input string\n";

# strip leading and trailing 0's
$s =~ s/^0+//;
$s =~ s/0+$//;

# prime the position list with the first '1' at position 0
my @p = (0);

# start at position 1, which is the second character
my $i = 1;

print "the string is $s\n\n";

while ($i < length($s)) {
   if (substr($s, $i, 1) eq '1') {
      print "found '1' at position $i\n";
      my @t = ();
      # assuming this is the middle '1', go through the positions
      # of all the prior '1's and check whether there's another '1'
      # in the correct position after this '1' to make a solution
      while (scalar @p) {
         # $p is the position of the prior '1'
         my $p = shift @p;
         # $j is the corresponding position for the following '1'
         my $j = 2 * $i - $p;
         # if $j is off the end of the string then we don't need to
         # check $p anymore
         next if ($j >= length($s));
         print "checking positions $p, $i, $j\n";
         if (substr($s, $j, 1) eq '1') {
            print "\nsolution found at positions $p, $i, $j\n";
            exit 0;
         }
         # if $j isn't off the end of the string, keep $p for next time
         push @t, $p;
      }
      @p = @t;
      # add this '1' to the list of '1' positions
      push @p, $i;
   }
   $i++;
}

print "\nno solution found\n";

Podczas skanowania 1, dodaj ich pozycje do listy. Dodając drugą i kolejne 1, porównaj je z każdą pozycją na liście do tej pory. Odstępy są równe currentOne (w środku) - previousOne (po lewej). Bit po prawej stronie to currentOne + odstęp. Jeśli jest 1, koniec.

Lista tych rośnie odwrotnie wraz z przestrzenią między nimi. Mówiąc prosto, jeśli masz dużo zer między 1 (jak w najgorszym przypadku), twoja lista znanych 1 będzie rosła dość wolno.

using System;
using System.Collections.Generic;

namespace spacedOnes
{
    class Program
    {
        static int[] _bits = new int[8] {128, 64, 32, 16, 8, 4, 2, 1};

        static void Main(string[] args)
        {
            var bytes = new byte[4];
            var r = new Random();
            r.NextBytes(bytes);
            foreach (var b in bytes) {
                Console.Write(getByteString(b));
            }
            Console.WriteLine();
            var bitCount = bytes.Length * 8;
            var done = false;
            var onePositions = new List<int>();
            for (var i = 0; i < bitCount; i++)
            {
                if (isOne(bytes, i)) {
                    if (onePositions.Count > 0) {
                        foreach (var knownOne in onePositions) {
                            var spacing = i - knownOne;
                            var k = i + spacing;
                            if (k < bitCount && isOne(bytes, k)) {
                                Console.WriteLine("^".PadLeft(knownOne + 1) + "^".PadLeft(spacing) + "^".PadLeft(spacing));
                                done = true;
                                break;
                            }
                        }
                    }
                    if (done) {
                        break;
                    }
                    onePositions.Add(i);
                }
            }
            Console.ReadKey();
        }

        static String getByteString(byte b) {
            var s = new char[8];
            for (var i=0; i<s.Length; i++) {
                s[i] = ((b & _bits[i]) > 0 ? '1' : '0');
            }
            return new String(s);
        }

        static bool isOne(byte[] bytes, int i)
        {
            var byteIndex = i / 8;
            var bitIndex = i % 8;
            return (bytes[byteIndex] & _bits[bitIndex]) > 0;
        }
    }
}

Pomyślałem, że dodam jeden komentarz przed zamieszczeniem 22. naiwnego rozwiązania problemu. W przypadku naiwnego rozwiązania nie musimy pokazywać, że liczba jedynek w ciągu wynosi co najwyżej O (log (n)), ale raczej że jest to najwyżej O (sqrt (n * log (n)).

Solver:

def solve(Str):
    indexes=[]
    #O(n) setup
    for i in range(len(Str)):
        if Str[i]=='1':
            indexes.append(i)

    #O((number of 1's)^2) processing
    for i in range(len(indexes)):
        for j in range(i+1, len(indexes)):
                            indexDiff = indexes[j] - indexes[i]
            k=indexes[j] + indexDiff
            if k<len(Str) and Str[k]=='1':
                return True
    return False

Zasadniczo jest trochę podobny do pomysłu i implementacji flybywire, ale patrzy w przyszłość, a nie wstecz.

Greedy String Builder:

#assumes final char hasn't been added, and would be a 1 
def lastCharMakesSolvable(Str):
    endIndex=len(Str)
    j=endIndex-1
    while j-(endIndex-j) >= 0:
        k=j-(endIndex-j)
        if k >= 0 and Str[k]=='1' and Str[j]=='1':
            return True
        j=j-1
    return False



def expandString(StartString=''):
    if lastCharMakesSolvable(StartString):
        return StartString + '0'
    return StartString + '1'

n=1
BaseStr=""
lastCount=0
while n<1000000:
    BaseStr=expandString(BaseStr)
    count=BaseStr.count('1')
    if count != lastCount:
        print(len(BaseStr), count)
    lastCount=count
    n=n+1

(Na swoją obronę, wciąż jestem na etapie rozumienia języka Python)

Ponadto, potencjalnie użyteczny wynik chciwego budowania strun, występuje raczej konsekwentny skok po uderzeniu w potęgę 2 w liczbie jedynek ... których nie byłem skłonny czekać, aż zobaczyłem uderzenie 2096.

strlength   # of 1's
    1    1
    2    2
    4    3
    5    4
   10    5
   14    8
   28    9
   41    16
   82    17
  122    32
  244    33
  365    64
  730    65
 1094    128
 2188    129
 3281    256
 6562    257
 9842    512
19684    513
29525    1024

Postaram się przedstawić podejście matematyczne. To bardziej początek niż koniec, więc każda pomoc, komentarz, a nawet sprzeczność - będą bardzo mile widziane. Jeśli jednak to podejście jest sprawdzone - algorytm polega na prostym wyszukiwaniu w ciągu.

1. Biorąc pod uwagę ustaloną liczbę spacji ki ciąg S, wyszukiwanie trioli k- spacji trwa O(n)- po prostu testujemy dla każdego warunku 0<=i<=(n-2k)if S[i]==S[i+k]==S[i+2k]. Test trwa O(1)i robimy to n-krazy, gdzie kjest stała, więc trwa O(n-k)=O(n).

2. Załóżmy, że istnieje odwrotna proporcja między liczbą 1's a maksymalną liczbą przestrzeni, których musimy szukać. To znaczy, że jeśli jest ich wiele 1, musi istnieć trójka i musi być dość gęsta; Jeśli jest tylko kilka 1, trójka (jeśli w ogóle) może być dość rzadka. Innymi słowy, mogę udowodnić, że jeśli mam wystarczająco dużo 1, taka trójka musi istnieć - a im więcej 1mam, tym trzeba znaleźć triolę gęstszą. Można to wytłumaczyć zasadą Pigeonhole - Mam nadzieję, że omówię to później.

3. Powiedz, że ma górną granicę k możliwej liczby miejsc, których muszę szukać. Teraz, każdy 1znajduje się S[i]musimy sprawdzić 1w S[i-1]i S[i+1], S[i-2]i S[i+2]... S[i-k]i S[i+k]. Trwa to O((k^2-k)/2)=O(k^2)dla każdego 1w S- ze względu na wzór sumowania serii Gaussa . Zauważ, że różni się to od sekcji 1 - mam kjako górną granicę liczby spacji, a nie jako stałą przestrzeń.

Musimy to udowodnić O(n*log(n)). Oznacza to, że musimy pokazać, że k*(number of 1's)jest to proporcjonalne dolog(n) .

Jeśli możemy to zrobić, algorytm jest trywialny - dla każdego, 1w Sktórego indeksie jest i, po prostu szukaj 1znaków z każdej strony aż do odległości k. Jeśli znaleziono dwa w tej samej odległości, wróć ii k. Ponownie, najtrudniejsza część polegałaby na znalezieniu ki udowodnieniu poprawności.

Byłbym bardzo wdzięczny za twoje komentarze tutaj - próbowałem znaleźć zależność między ka liczbą 1na mojej tablicy, jak dotąd bez powodzenia.

Założenie:

Po prostu źle, mówiąc o log (n) liczbie górnej granicy jedynek

EDYTOWAĆ:

Teraz odkryłem, że używając liczb Cantora (jeśli są poprawne), gęstość na zbiorze wynosi (2/3) ^ Log_3 (n) (co za dziwna funkcja) i zgadzam się, gęstość log (n) / n jest zbyt silna.

Jeśli jest to górna granica, istnieje algorytm, który rozwiązuje ten problem w złożoności czasowej co najmniej O (n * (3/2) ^ (log (n) / log (3))) i O ((3/2) ^ ( log (n) / log (3))) złożoność przestrzeni. (sprawdź odpowiedź Justice na algorhitm)

To wciąż jest o wiele lepsze niż O (n ^ 2)

Ta funkcja ((3/2) ^ (log (n) / log (3))) naprawdę wygląda na pierwszy rzut oka jak n * log (n).

Jak otrzymałem tę formułę?

Umieszczanie numeru Cantors na sznurku.
Załóżmy, że długość łańcucha wynosi 3 ^ p == n
Na każdym etapie tworzenia łańcucha Cantor zachowujesz 2/3 dotychczasowej liczby jedynek. Zastosuj to p razy.

To oznacza (n * ((2/3) ^ p)) -> (((3 ^ p)) * ((2/3) ^ p)) pozostałe i po uproszczeniu 2 ^ p. To oznacza 2 ^ p jedynek w 3 ^ p łańcuchach -> (3/2) ^ p jedynek. Podstaw p = log (n) / log (3) i pobierz
((3/2) ^ (log (n) / log (3)))

A co z prostym rozwiązaniem O (n), z przestrzenią O (n ^ 2)? (Przyjmuje założenie, że wszystkie operatory bitowe działają w O (1).)

Algorytm zasadniczo działa w czterech etapach:

Etap 1: Dla każdego bitu w pierwotnej liczbie sprawdź, jak daleko są one, ale rozważ tylko jeden kierunek. (Rozważyłem wszystkie bity w kierunku najmniej znaczącego bitu.)

Etap 2: Odwróć kolejność bitów na wejściu;

Etap 3: Ponownie wykonaj krok 1 na wejściu odwróconym.

Etap 4: Porównaj wyniki z Etapu 1 i Etapu 3. Jeśli jakiekolwiek bity są równo rozmieszczone powyżej ORAZ poniżej, musimy mieć trafienie.

Należy pamiętać, że żaden krok w powyższym algorytmie nie trwa dłużej niż O (n). ^ _ ^

Dodatkową korzyścią jest to, że algorytm ten znajdzie WSZYSTKIE równomiernie rozmieszczone z KAŻDEJ liczby. Na przykład, jeśli otrzymasz wynik „0x0005”, to są równo rozmieszczone jednostki w odległości 1 i 3 jednostek

Tak naprawdę nie próbowałem optymalizować poniższego kodu, ale jest to kompilowalny kod C #, który wydaje się działać.

using System;

namespace ThreeNumbers
{
    class Program
    {
        const int uint32Length = 32;

        static void Main(string[] args)
        {
            Console.Write("Please enter your integer: ");
            uint input = UInt32.Parse(Console.ReadLine());

            uint[] distancesLower = Distances(input);
            uint[] distancesHigher = Distances(Reverse(input));

            PrintHits(input, distancesLower, distancesHigher);
        }

        /// <summary>
        /// Returns an array showing how far the ones away from each bit in the input.  Only 
        /// considers ones at lower signifcant bits.  Index 0 represents the least significant bit 
        /// in the input.  Index 1 represents the second least significant bit in the input and so 
        /// on.  If a one is 3 away from the bit in question, then the third least significant bit 
        /// of the value will be sit.
        /// 
        /// As programed this algorithm needs: O(n) time, and O(n*log(n)) space.  
        /// (Where n is the number of bits in the input.)
        /// </summary>
        public static uint[] Distances(uint input)
        {
            uint[] distanceToOnes = new uint[uint32Length];
            uint result = 0;

            //Sets how far each bit is from other ones. Going in the direction of LSB to MSB
            for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
            {
                distanceToOnes[arrayIndex] = result;
                result <<= 1;

                if ((input & bitIndex) != 0)
                {
                    result |= 1;
                }
            }

            return distanceToOnes;
        }

        /// <summary>
        /// Reverses the bits in the input.
        /// 
        /// As programmed this algorithm needs O(n) time and O(n) space.  
        /// (Where n is the number of bits in the input.)
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        public static uint Reverse(uint input)
        {
            uint reversedInput = 0;
            for (uint bitIndex = 1; bitIndex != 0; bitIndex <<= 1)
            {
                reversedInput <<= 1;
                reversedInput |= (uint)((input & bitIndex) != 0 ? 1 : 0);
            }

            return reversedInput;
        }

        /// <summary>
        /// Goes through each bit in the input, to check if there are any bits equally far away in 
        /// the distancesLower and distancesHigher
        /// </summary>
        public static void PrintHits(uint input, uint[] distancesLower, uint[] distancesHigher)
        {
            const int offset = uint32Length - 1;

            for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex)
            {
                //hits checks if any bits are equally spaced away from our current value
                bool isBitSet = (input & bitIndex) != 0;
                uint hits = distancesLower[arrayIndex] & distancesHigher[offset - arrayIndex];

                if (isBitSet && (hits != 0))
                {
                    Console.WriteLine(String.Format("The {0}-th LSB has hits 0x{1:x4} away", arrayIndex + 1, hits));
                }
            }
        }
    }
}

Ktoś prawdopodobnie skomentuje, że dla żadnej wystarczająco dużej liczby operacje bitowe nie mogą być wykonywane w O (1). Miałbyś rację. Przypuszczam jednak, że każde rozwiązanie, które wykorzystuje dodawanie, odejmowanie, mnożenie lub dzielenie (czego nie można zrobić przez przesuwanie), również miałoby ten problem.

Poniżej znajduje się rozwiązanie. Tu i tam mogą wystąpić drobne błędy, ale pomysł jest rozsądny.

Edycja: to nie jest n * log (n)

PSEUDO KOD:

foreach character in the string
  if the character equals 1 {         
     if length cache > 0 { //we can skip the first one
        foreach location in the cache { //last in first out kind of order
           if ((currentlocation + (currentlocation - location)) < length string)
              if (string[(currentlocation + (currentlocation - location))] equals 1)
                 return found evenly spaced string
           else
              break;
        }
     }
     remember the location of this character in a some sort of cache.
  }

return didn't find evenly spaced string

Kod C #:

public static Boolean FindThreeEvenlySpacedOnes(String str) {
    List<int> cache = new List<int>();

    for (var x = 0; x < str.Length; x++) {
        if (str[x] == '1') {
            if (cache.Count > 0) {
                for (var i = cache.Count - 1; i > 0; i--) {
                    if ((x + (x - cache[i])) >= str.Length)
                        break;

                    if (str[(x + (x - cache[i]))] == '1')
                        return true;                            
                }
            }
            cache.Add(x);                    
        }
    }

    return false;
}

Jak to działa:

iteration 1:
x
|
101101001
// the location of this 1 is stored in the cache

iteration 2:
 x
 | 
101101001

iteration 3:
a x b 
| | | 
101101001
//we retrieve location a out of the cache and then based on a 
//we calculate b and check if te string contains a 1 on location b

//and of course we store x in the cache because it's a 1

iteration 4:
  axb  
  |||  
101101001

a  x  b  
|  |  |  
101101001


iteration 5:
    x  
    |  
101101001

iteration 6:
   a x b 
   | | | 
101101001

  a  x  b 
  |  |  | 
101101001
//return found evenly spaced string

Oczywiście musimy przynajmniej sprawdzać pęczki trojaczków w tym samym czasie, więc musimy jakoś skompresować czeki. Mam algorytm kandydata, ale analiza złożoności czasowej przekracza mój próg czasowy *.

Zbuduj drzewo, w którym każdy węzeł ma troje dzieci, a każdy węzeł zawiera całkowitą liczbę jedynek na swoich liściach. Zbuduj również połączoną listę ponad 1. Przypisz każdemu węzłowi dozwolony koszt proporcjonalny do zakresu, który obejmuje. Dopóki czas spędzony w każdym węźle mieści się w budżecie, będziemy mieć algorytm O (n lg n).

-

Zacznij od korzenia. Jeśli kwadrat całkowitej liczby jedynek poniżej jest mniejszy niż dopuszczalny koszt, zastosuj naiwny algorytm. W przeciwnym razie powtórz na swoich dzieciach.

Teraz albo wróciliśmy w ramach budżetu, albo wiemy, że w jednym z dzieci nie ma żadnych prawidłowych trojaczków. Dlatego musimy sprawdzić trójki między węzłami.

Teraz robi się niesamowicie bałagan. Zasadniczo chcemy powtórzyć potencjalne zestawy dzieci, jednocześnie ograniczając zakres. Gdy tylko zakres jest na tyle ograniczony, że naiwny algorytm będzie działał w ramach budżetu, robisz to. Ciesz się wdrażaniem tego, bo gwarantuję, że będzie to żmudne. Jest z tuzin przypadków.

-

Uważam, że algorytm zadziała, ponieważ sekwencje bez prawidłowych trojaczków wydają się przechodzić naprzemiennie między pęczkami jedynek i wieloma zerami. Skutecznie dzieli pobliską przestrzeń wyszukiwania, a drzewo naśladuje ten podział.

Czas działania algorytmu wcale nie jest oczywisty. Opiera się na nietrywialnych właściwościach sekwencji. Jeśli 1 są naprawdę rzadkie, naiwny algorytm będzie działał w ramach budżetu. Jeśli jedynki są gęste, należy od razu znaleźć dopasowanie. Ale jeśli gęstość jest „w sam raz” (np. Blisko ~ n ^ 0,63, co można osiągnąć ustawiając wszystkie bity na pozycjach bez cyfry „2” w bazie 3), nie wiem, czy zadziała. Musiałbyś udowodnić, że efekt rozszczepiania jest wystarczająco silny.

Nie ma tu teoretycznej odpowiedzi, ale napisałem szybki program w języku Java, aby zbadać zachowanie w czasie wykonywania w funkcji k i n, gdzie n to całkowita długość bitu, ak to liczba jedynek. Jestem z kilkoma odpowiadającymi, którzy twierdzą, że „zwykły” algorytm, który sprawdza wszystkie pary pozycji bitów i szuka trzeciego bitu, mimo że wymagałby O (k ^ 2) w najgorszym przypadku, w rzeczywistość, ponieważ najgorszy przypadek wymaga rzadkich bitstringów, to O (n ln n).

W każdym razie oto program poniżej. Jest to program w stylu Monte-Carlo, który przeprowadza dużą liczbę prób NTRIALS dla stałej n i losowo generuje zestawy bitów dla zakresu wartości k przy użyciu procesów Bernoulliego z gęstością jedynkową ograniczoną między limitami, które można określić, i rejestruje czas wykonywania znalezienia lub niepowodzenia znalezienia trójki równomiernie rozmieszczonych, czas mierzony w krokach, a NIE w czasie procesora. Uruchomiłem go dla n = 64, 256, 1024, 4096, 16384 * (nadal działa), najpierw test z 500000 prób, aby zobaczyć, które wartości k zajmują najdłuższy czas działania, a następnie kolejny test z 5000000 prób z zawężonymi próbami- skup się na gęstości, aby zobaczyć, jak wyglądają te wartości. Najdłuższe czasy pracy zdarzają się przy bardzo rzadkiej gęstości (np. Dla n = 4096 szczyty czasu pracy znajdują się w zakresie k = 16-64, z łagodnym szczytem dla średniego czasu pracy przy 4212 krokach przy k = 31, maksymalny czas pracy osiągnął poziom 5101 kroków przy k = 58). Wygląda na to, że dla najgorszego kroku O (k ^ 2) wymagałoby to bardzo dużych wartości N, aby były większe niż krok O (n), w którym przeszukuje się ciąg bitów, aby znaleźć indeksy pozycji 1.

package com.example.math;

import java.io.PrintStream;
import java.util.BitSet;
import java.util.Random;

public class EvenlySpacedOnesTest {
    static public class StatisticalSummary
    {
        private int n=0;
        private double min=Double.POSITIVE_INFINITY;
        private double max=Double.NEGATIVE_INFINITY;
        private double mean=0;
        private double S=0;

        public StatisticalSummary() {}
        public void add(double x) {
            min = Math.min(min, x);
            max = Math.max(max, x);
            ++n;
            double newMean = mean + (x-mean)/n;
            S += (x-newMean)*(x-mean);
            // this algorithm for mean,std dev based on Knuth TAOCP vol 2
            mean = newMean;
        }
        public double getMax() { return (n>0)?max:Double.NaN; }
        public double getMin() { return (n>0)?min:Double.NaN; }
        public int getCount() { return n; }
        public double getMean() { return (n>0)?mean:Double.NaN; }
        public double getStdDev() { return (n>0)?Math.sqrt(S/n):Double.NaN; } 
        // some may quibble and use n-1 for sample std dev vs population std dev    
        public static void printOut(PrintStream ps, StatisticalSummary[] statistics) {
            for (int i = 0; i < statistics.length; ++i)
            {
                StatisticalSummary summary = statistics[i];
                ps.printf("%d\t%d\t%.0f\t%.0f\t%.5f\t%.5f\n",
                        i,
                        summary.getCount(),
                        summary.getMin(),
                        summary.getMax(),
                        summary.getMean(),
                        summary.getStdDev());
            }
        }
    }

    public interface RandomBernoulliProcess // see http://en.wikipedia.org/wiki/Bernoulli_process
    {
        public void setProbability(double d);
        public boolean getNextBoolean();
    }

    static public class Bernoulli implements RandomBernoulliProcess
    {
        final private Random r = new Random();
        private double p = 0.5;
        public boolean getNextBoolean() { return r.nextDouble() < p; }
        public void setProbability(double d) { p = d; }
    }   
    static public class TestResult {
        final public int k;
        final public int nsteps;
        public TestResult(int k, int nsteps) { this.k=k; this.nsteps=nsteps; } 
    }

    ////////////
    final private int n;
    final private int ntrials;
    final private double pmin;
    final private double pmax;
    final private Random random = new Random();
    final private Bernoulli bernoulli = new Bernoulli();
    final private BitSet bits;
    public EvenlySpacedOnesTest(int n, int ntrials, double pmin, double pmax) {
        this.n=n; this.ntrials=ntrials; this.pmin=pmin; this.pmax=pmax;
        this.bits = new BitSet(n);
    }

    /*
     * generate random bit string
     */
    private int generateBits()
    {
        int k = 0; // # of 1's
        for (int i = 0; i < n; ++i)
        {
            boolean b = bernoulli.getNextBoolean();
            this.bits.set(i, b);
            if (b) ++k;
        }
        return k;
    }

    private int findEvenlySpacedOnes(int k, int[] pos) 
    {
        int[] bitPosition = new int[k];
        for (int i = 0, j = 0; i < n; ++i)
        {
            if (this.bits.get(i))
            {
                bitPosition[j++] = i;
            }
        }
        int nsteps = n; // first, it takes N operations to find the bit positions.
        boolean found = false;
        if (k >= 3) // don't bother doing anything if there are less than 3 ones. :(
        {       
            int lastBitSetPosition = bitPosition[k-1];
            for (int j1 = 0; !found && j1 < k; ++j1)
            {
                pos[0] = bitPosition[j1];
                for (int j2 = j1+1; !found && j2 < k; ++j2)
                {
                    pos[1] = bitPosition[j2];

                    ++nsteps;
                    pos[2] = 2*pos[1]-pos[0];
                    // calculate 3rd bit index that might be set;
                    // the other two indices point to bits that are set
                    if (pos[2] > lastBitSetPosition)
                        break;
                    // loop inner loop until we go out of bounds

                    found = this.bits.get(pos[2]);
                    // we're done if we find a third 1!
                }
            }
        }
        if (!found)
            pos[0]=-1;
        return nsteps;
    }

    /*
     * run an algorithm that finds evenly spaced ones and returns # of steps.
     */
    public TestResult run()
    {
        bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
        // probability of bernoulli process is randomly distributed between pmin and pmax

        // generate bit string.
        int k = generateBits();
        int[] pos = new int[3];
        int nsteps = findEvenlySpacedOnes(k, pos);
        return new TestResult(k, nsteps); 
    }

    public static void main(String[] args)
    {
        int n;
        int ntrials;
        double pmin = 0, pmax = 1;
        try {
            n = Integer.parseInt(args[0]);
            ntrials = Integer.parseInt(args[1]);
            if (args.length >= 3)
                pmin = Double.parseDouble(args[2]);
            if (args.length >= 4)
                pmax = Double.parseDouble(args[3]);
        }
        catch (Exception e)
        {
            System.out.println("usage: EvenlySpacedOnesTest N NTRIALS [pmin [pmax]]");
            System.exit(0);
            return; // make the compiler happy
        }

        final StatisticalSummary[] statistics;
        statistics=new StatisticalSummary[n+1];
        for (int i = 0; i <= n; ++i)
        {
            statistics[i] = new StatisticalSummary();
        }

        EvenlySpacedOnesTest test = new EvenlySpacedOnesTest(n, ntrials, pmin, pmax);
        int printInterval=100000;
        int nextPrint = printInterval;
        for (int i = 0; i < ntrials; ++i)
        {
            TestResult result = test.run();
            statistics[result.k].add(result.nsteps);
            if (i == nextPrint)
            {
                System.err.println(i);
                nextPrint += printInterval;
            }
        }
        StatisticalSummary.printOut(System.out, statistics);
    }
}

# <algorithm>
def contains_evenly_spaced?(input)
  return false if input.size < 3
  one_indices = []
  input.each_with_index do |digit, index|
    next if digit == 0
    one_indices << index
  end
  return false if one_indices.size < 3
  previous_indexes = []
  one_indices.each do |index|
    if !previous_indexes.empty?
      previous_indexes.each do |previous_index|
        multiple = index - previous_index
        success_index = index + multiple
        return true if input[success_index] == 1
      end
    end
    previous_indexes << index
  end
  return false
end
# </algorithm>

def parse_input(input)
  input.chars.map { |c| c.to_i }
end

Mam problem z najgorszym scenariuszem z milionami cyfr. Fuzzing od /dev/urandomzasadniczo daje O (n), ale wiem, że najgorszy przypadek jest gorszy. Po prostu nie mogę powiedzieć, o ile gorzej. W przypadku małych n, znalezienie danych wejściowych w pobliżu jest trywialne 3*n*log(n), ale zaskakująco trudno jest odróżnić je od innej kolejności wzrostu dla tego konkretnego problemu.

Czy ktoś, kto pracował nad danymi wejściowymi z najgorszego przypadku, może wygenerować ciąg o długości większej niż, powiedzmy, sto tysięcy?

Możliwa jest adaptacja algorytmu Rabina-Karpa. Jego złożoność wynosi 0 (n), więc może ci pomóc.

Spójrz na http://en.wikipedia.org/wiki/Rabin-Karp_string_search_algorithm

Czy to może być rozwiązanie? I ', nie jestem pewien, czy to O (nlogn), ale moim zdaniem jest lepsze niż O (n²), ponieważ jedynym sposobem, aby nie znaleźć potrójnej, byłby rozkład liczb pierwszych.

Jest miejsce na ulepszenia, druga znaleziona 1 może być następną pierwszą 1. Również bez sprawdzania błędów.

#include <iostream>

#include <string>

int findIt(std::string toCheck) {
    for (int i=0; i<toCheck.length(); i++) {
        if (toCheck[i]=='1') {
            std::cout << i << ": " << toCheck[i];
            for (int j = i+1; j<toCheck.length(); j++) {
                if (toCheck[j]=='1' && toCheck[(i+2*(j-i))] == '1') {
                    std::cout << ", " << j << ":" << toCheck[j] << ", " << (i+2*(j-i)) << ":" << toCheck[(i+2*(j-i))] << "    found" << std::endl;
                    return 0;
                }
            }
        }
    }
    return -1;
}

int main (int agrc, char* args[]) {
    std::string toCheck("1001011");
    findIt(toCheck);
    std::cin.get();
    return 0;
}

Myślę, że ten algorytm ma złożoność O (n log n) (C ++, DevStudio 2k5). Teraz nie znam szczegółów, jak analizować algorytm w celu określenia jego złożoności, więc dodałem do kodu pewne metryki zbierające informacje. Kod zlicza liczbę testów wykonanych na sekwencji jedynek i zer dla dowolnego podanego wejścia (mam nadzieję, że nie zrobiłem kulek z algorytmu). Możemy porównać rzeczywistą liczbę testów z wartością O i sprawdzić, czy istnieje korelacja.

#include <iostream>
using namespace std;

bool HasEvenBits (string &sequence, int &num_compares)
{
  bool
    has_even_bits = false;

  num_compares = 0;

  for (unsigned i = 1 ; i <= (sequence.length () - 1) / 2 ; ++i)
  {
    for (unsigned j = 0 ; j < sequence.length () - 2 * i ; ++j)
    {
      ++num_compares;
      if (sequence [j] == '1' && sequence [j + i] == '1' && sequence [j + i * 2] == '1')
      {
        has_even_bits = true;
        // we could 'break' here, but I want to know the worst case scenario so keep going to the end
      }
    }
  }

  return has_even_bits;
}

int main ()
{
  int
    count;

  string
    input = "111";

  for (int i = 3 ; i < 32 ; ++i)
  {
    HasEvenBits (input, count);
    cout << i << ", " << count << endl;
    input += "0";
  }
}

Ten program wyprowadza liczbę testów dla każdego łańcucha o długości do 32 znaków. Oto wyniki:

 n  Tests  n log (n)
=====================
 3     1     1.43
 4     2     2.41
 5     4     3.49
 6     6     4.67
 7     9     5.92
 8    12     7.22
 9    16     8.59
10    20    10.00
11    25    11.46
12    30    12.95
13    36    14.48
14    42    16.05
15    49    17.64
16    56    19.27
17    64    20.92
18    72    22.59
19    81    24.30
20    90    26.02
21   100    27.77
22   110    29.53
23   121    31.32
24   132    33.13
25   144    34.95
26   156    36.79
27   169    38.65
28   182    40.52
29   196    42.41
30   210    44.31
31   225    46.23

Dodałem również wartości „n log n”. Wykreśl je za pomocą wybranego narzędzia graficznego, aby zobaczyć korelację między dwoma wynikami. Czy ta analiza obejmuje wszystkie wartości n? Nie wiem