Algorytm wykluczania numerów

Question

Otrzymujesz liczbę całkowitą N, która pasuje do długich (mniej niż 2^63-1) i 50 innych liczb całkowitych. Twoim zadaniem jest dowiedzieć się, ile liczb od 1 do N nie zawiera żadnego z 50 liczb jako podłańcuchów?

To pytanie pochodzi z wywiadu.

Answer 1

Nie określono podstawy, ale przyjmę dziesiętny bez utraty ogólności.

Po pierwsze, rozpoznaj, że jest to problem z ciągami, a nie numeryczny.

Utwórz automat skończony A, aby rozpoznać 50 liczb całkowitych jako podciągi innych ciągów. Na przykład, dwie liczby całkowite 44 i 3 są rozpoznawane jako podciągi przez RE

^.*(44|3).*$ 

Budowanie skończony automat B rozpoznać wszystkie numery mniej niż N. Na przykład, aby rozpoznać od 1 do 27 (włącznie), w układzie dziesiętnym, które mogą być osiągnięte poprzez gromadzenie RE

^([1-9]|1[0-9]|2[0-7])$ 

obliczyć przecięcia C z automatów i B, który z kolei jest An FA.

Użyj algorytmu do programowania dynamicznego, aby obliczyć rozmiar języka rozpoznawanego przez C. Odejmij od rozmiaru języka rozpoznanego przez A, obliczonego przez ten sam algorytm.

(ja nie twierdzę, że to jest asymptotycznie optymalne, ale było to na tyle szybko, aby rozwiązać wiele problemów Euler projektu :)

Answer 2

to tylko wyjaśnienie co larsmans już napisałem. Jeśli podoba ci się ta odpowiedź, zagłosuj na niego dodatkowo.

Automat skończony, FA, jest po prostu zbiorem stanach oraz zasady mówią, że jeśli jesteś w stanie S i następna postać, którą są karmione jest c następnie przejście do stanu T. Dwa z państw są wyjątkowe. Jeden oznacza "zacznij tutaj", a drugi oznacza "Z powodzeniem dopasowałem". Jedna z postaci jest wyjątkowa i oznacza "właśnie zakończony ciąg". Więc weź ciąg i skończony automat, zacznij od stanu początkowego, kontynuuj wprowadzanie znaków do maszyny i zmienianie stanów. Nie uda ci się dopasować, jeśli dasz dowolnemu państwu nieoczekiwany sygnał wejściowy. Udaje Ci się dopasować, jeśli kiedykolwiek osiągniesz stan "Z powodzeniem dopasowałem".

Teraz jest dobrze znany algorytm konwersji wyrażenia regularnego do skończonego automatu, który dopasowuje ciąg znaków tylko wtedy, gdy pasuje do tego wyrażenia regularnego. (Jeśli czytałeś o wyrażeniach regularnych, to działają silniki DFA.) Aby zilustrować, użyję wzorca ^.*(44|3).*$, co oznacza "początek ciągu znaków, dowolna liczba znaków, a następnie 44 lub 3, a następnie dowolna liczba znaków. liczba znaków, a następnie koniec ciągu."

etykieta

Zacznijmy wszystkich pozycjach możemy być w wyrażeniu regularnym, gdy szukamy następnego znaku: ^.*(4 B 4|3) C .*$

Państwa z naszych stałych silnika ekspresji będzie podzbiory tych pozycji, a stan specjalny jest dopasowany, wynikiem przejścia stanu będzie zbiór stanów, do których moglibyśmy się dostać, gdybyśmy byli na tej pozycji, i zobaczylibyśmy szczególny charakter. Nasza pozycja początkowa znajduje się na początku RE , która jest {A}. Oto stany, które można osiągnąć:

S1: {A} # start 
S2: {A, B} 
S3: {A, C} 
S4: {A, B, C} 
S5: matched 

Oto zasady przejściowe:

S1: 
    3: S3 
    4: S2 
    end of string: FAIL 
    any other char: S1 
S2: 
    3: S3 
    4: S3 
    end of string: FAIL 
    any other char: S1 
S3: 
    4: S4 
    end of string: S5 (match) 
    any other char: S3 
S4: 
    end of string: S5 (match) 
    any other char: S4 

Teraz, jeśli wziąć dowolny ciąg znaków, start, który w stanie S1 i postępować zgodnie z zasadami, będzie zgodne ze wzorcem. Proces ten może być długi i żmudny, ale na szczęście można go zautomatyzować. Domyślam się, że larsmans zautomatyzował go na własny użytek. (Uwaga techniczna, rozszerzenie z "pozycji w RE" do "zestawów pozycji, na których możesz być" może być wykonane z góry, jak tutaj, lub w czasie wykonywania. Dla większości REs lepiej jest zrobić to z przodu , jak tutaj, ale niewielki ułamek patologicznych przykładów kończy się na bardzo dużej liczbie stanów, a może być lepiej wykonać je w czasie wykonywania).

Możemy to zrobić z dowolnym wyrażeniem regularnym. Na przykład ^([1-9]|1[0-9]|2[0-7])$ można dostać oznakowane: ^([1-9]|1 B [0-9]|2 C [0-7]) D $ i otrzymujemy stany:

T1: {A} 
T2: {D} 
T3: {B, D} 
T4: {C, D} 

i przejścia:

T1: 
    1: T3 
    2: T4 
    3-9: T2 
    any other char: FAIL 
T2: 
    end of string: MATCH 
    any other char: FAIL 
T3: 
    0-9: T2 
    end of string: MATCH 
    any other char: FAIL 
T4: 
    0-7: T2 
    end of string: MATCH 
    any other char: FAIL 

OK, więc wiemy, co to jest wyrażenie regularne, jak skończony automat i jak się z nim wiążą. Jakie jest skrzyżowanie dwóch skończonych automatów? Jest to tylko automat skończony, który pasuje, gdy oba skończone automaty indywidualnie pasują, a inaczej nie pasuje. Łatwo go skonstruować, jego zbiór stanów jest po prostu zbiorem par stanu w jednym, a stanem w drugim. Jego reguła przejścia polega na tym, aby zastosować regułę przejściową dla każdego członka niezależnie, jeśli jedna z nich nie powiedzie się, jeśli obie spełniają oba.

Dla powyższej pary, faktycznie wykonujemy przecięcie na numerze 13. Zaczynamy w stanie (S1, T1)

state: (S1, T1) next char: 1 
state: (S1, T3) next char: 3 
state: (S3, T2) next char: end of string 
state: (matched, matched) -> matched 

A potem od liczby 14.

state: (S1, T1) next char: 1 
state: (S1, T3) next char: 4 
state: (S2, T2) next char: end of string 
state: (FAIL, matched) -> FAIL 

Teraz dochodzimy do sedna tego. Biorąc pod uwagę ostatnie skończone automaty, możemy użyć programowania dynamicznego, aby dowiedzieć się, ile ciągów pasuje do niego. Tutaj jest to, że kalkulacja:

0 chars: 
    (S1, T1): 1 
    -> (S1, T3): 1 # 1 
    -> (S1, T4): 1 # 2 
    -> (S3, T2): 1 # 3 
    -> (S2, T2): 1 # 4 
    -> (S1, T2): 5 # 5-9 
1 chars: 
    (S1: T2): 5  # dead end 
    (S1, T3): 1 
    -> (S1, T2): 8 # 0-2, 5-9 
    -> (S2, T2): 1 # 3 
    -> (S3, T2): 1 # 4 
    (S1, T4): 1 
    -> (S1, T2): 6 # 0-2, 5-7 
    -> (S2, T2): 1 # 3 
    -> (S3, T2): 1 # 4 
    (S2, T2): 1  # dead end 
    (S3, T2): 1 
    -> match: 1 # end of string 
2 chars: 
    (S1, T2): 14  # dead end 
    (S2, T2): 2  # dead end 
    (S3, T2): 2 
    -> match  2 # end of string 
    match: 1 
    -> match  1 # carry through the count 
3 chars: 
    match: 3 

OK, to dużo pracy, ale okazało się, że istnieją 3 ciągi pasujących zarówno tych zasad równocześnie. Zrobiliśmy to w sposób, który można zautomatyzować i skalować na znacznie większą liczbę osób.

Oczywiście pierwotnie postawione pytanie brzmiało, ile dopasowało drugie, ale nie pierwsze. Wiemy, że 27 pasuje do drugiej reguły, 3 pasują do siebie, więc 24 musi pasować do drugiej reguły, ale nie do pierwszej.

Jak już powiedziałem, jest to po prostu wyjaśnione rozwiązanie larsmans. Jeśli czegoś się nauczyłeś, przekaż mu głos, zagłosuj na jego odpowiedź. Jeśli ten materiał brzmi interesująco, kup książkę taką jak Progamming Language Pragmatics i dowiedz się więcej na temat skończonych automatów, parsowania, kompilacji i tym podobnych. Jest to bardzo dobry zestaw umiejętności i zdecydowanie zbyt wielu programistów tego nie robi.