Algoritmo per l'esclusione dei numeri

Question

Viene assegnato un numero intero N che si adatta a valori di stringa lunghi (meno di 2^63-1) e altri 50. Il tuo compito è di scoprire quanti numeri da 1 a N non contengono nessuno dei 50 numeri come sottostringa?

Questa domanda è da un'intervista.

Answer 1

Non hai specificato una base, ma assumerò decimale senza perdita di generalità.

Innanzitutto, riconoscere che si tratta di un problema di stringa, non numerico.

Costruire un automa finito A per riconoscere i 50 numeri interi come sottostringhe di altre stringhe. Ad esempio, i due interi 44 e 3 sono riconosciuti come sottostringhe dalla RE

^.*(44|3).*$ 

costruire un automa finito B riconoscere tutti i numeri inferiori N. Ad esempio, a riconoscere da 1 a 27 (compreso) a decimale, che può essere raggiunto dalla compilazione del RE

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

Calcola l'intersezione C dell'automa A e B, che è a sua volta un FA.

Utilizzare un algoritmo di programmazione dinamica per calcolare la dimensione della lingua riconosciuta da C. Sottrai quella dalla dimensione della lingua riconosciuta da A, calcolata dallo stesso algoritmo.

(Non sto affermando che questo è asintoticamente ottimale, ma è stato un abbastanza veloce per risolvere un sacco di problemi di Project Euler :)

Answer 2

questa è solo una spiegazione di ciò larsmans già scritto. Se ti piace questa risposta, per favore votalo in aggiunta.

Un automa a stati finiti, FA, è solo un insieme di stati , e le regole dicendo che se si è in stato di S e il carattere successivo si è Fed è c allora la transizione allo stato T. Due degli stati sono speciali. Uno significa "inizia qui" e l'altro significa "sono riuscito ad abbinarlo". Uno dei personaggi è speciale e significa "la stringa appena terminata". Quindi prendi una corda e un automa finito, inizia nello stato di partenza, continua ad alimentare i personaggi nella macchina e cambia gli stati. Non riesci a eguagliare se dai qualsiasi input inatteso di stato. Se riesci a raggiungere lo stato "Ho abbinato correttamente" riesci ad abbinare.

Ora c'è un algoritmo ben noto per convertire un'espressione regolare in un automone finito che corrisponde a una stringa se e solo se tale espressione regolare corrisponde. (Se hai letto di espressioni regolari, questo è il modo in cui funzionano i motori DFA.) Per illustrare userò il modello ^.*(44|3).*$ che significa "inizio della stringa, qualsiasi numero di caratteri, seguito da 44 o 3, seguito da qualsiasi numero di caratteri, seguito dalla fine della stringa."

etichetta

Prima di lasciare tutte le posizioni che può essere in nell'espressione regolare quando stiamo cercando il carattere successivo: ^ A .*(4 B 4|3) C .*$

Gli stati del nostro motore di espressioni regolari saranno sottoinsiemi di quelle posizioni, e lo stato speciale corrispondente.Il risultato di una transizione di stato sarà l'insieme di stati che potremmo ottenere se fossimo in quella posizione, e vedessimo un personaggio particolare.La nostra posizione di partenza è all'inizio della RE , che è {A}. Ecco gli stati che possono essere raggiunti:

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

Ecco le regole di transizione:

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 

Ora, se si prende qualsiasi stringa, dall'inizio che in stato S1, e seguire le regole, si corrisponde a quello schema. Il processo può essere lungo e noioso, ma per fortuna può essere automatizzato. La mia ipotesi è che i larsman l'abbiano automatizzato per suo uso personale. (Nota tecnica: l'espansione da "posizioni in RE" a "serie di posizioni in cui potresti trovarti" può essere fatta in anticipo, come qui o in fase di esecuzione. Per la maggior parte dei RE è meglio farlo in anticipo , come qui. Ma una piccola frazione di esempi patologici finirà con un numero molto grande di stati, e può essere meglio fare quelli in fase di esecuzione.)

Possiamo farlo con qualsiasi espressione regolare. Per esempio ^([1-9]|1[0-9]|2[0-7])$ può ottenere con l'etichetta: ^ A ([1-9]|1 B [0-9]|2 C [0-7]) D $ e otteniamo gli stati:

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

e transizioni:

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, quindi sappiamo che cosa un'espressione regolare è, che automa finito e come si relazionano. Qual è l'intersezione di due automi finiti? È solo un automa finito che corrisponde quando entrambi gli automi finiti corrispondono individualmente, e in caso contrario non riesce a eguagliare. È facile da costruire, il suo insieme di stati è solo l'insieme di coppie di uno stato nell'uno e uno stato nell'altro. La sua regola di transizione consiste nell'applicare la regola di transizione per ogni membro in modo indipendente, se uno dei due fallisce l'intero, se entrambi corrispondono entrambi.

Per la coppia di cui sopra, eseguiamo effettivamente l'intersezione sul numero 13. Partiamo in stato (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 

E poi sul numero 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 

Ora veniamo al punto intero di questo. Dato che gli automi finiti finali, possiamo usare la programmazione dinamica per capire quante stringhe ci sono che lo abbinano. Ecco che il calcolo:

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, questo è un sacco di lavoro, ma abbiamo scoperto che ci sono 3 stringhe che corrispondono a entrambe queste regole contemporaneamente. E lo abbiamo fatto in un modo che è automatizzabile e scalabile a numeri molto più grandi.

Ovviamente la domanda che ci poneva originariamente era quanti ne corrispondevano, ma non il primo. Bene, sappiamo che 27 corrisponde alla seconda regola, 3 corrispondono entrambe, quindi 24 deve corrispondere alla seconda regola ma non alla prima.

Come ho detto prima, questa è solo una soluzione larsman chiarita. Se hai imparato qualcosa, votalo, vota per la sua risposta. Se questo materiale sembra interessante, vai a comprare un libro come Progamming Language Pragmatic e impara molto di più sugli automi finiti, l'analisi, la compilazione e simili. È uno skillet molto buono da avere e troppi programmatori no.