Ciao ragazzi, sto implementando un piccolo algoritmo, naturalmente in python, per la ricerca di parole (disponibili in un dizionario), che corrispondono alle lettere di una stringa. Faccio un esempio: Se nella stringa:

lettereInput = "abnciay"

e la parola dal dizionario:

parolaDizionario = "cabina"

Volevo sapere se con le lettere 'abnciay' posso creare la parola 'cabina'. Avevo pensato di creare dei cicli for dove il primo itera le parole del dizionario, il secondo le lettere del dizionario, il terzo le lettere della stringa lettereInput.

Pensavo di adottare questo algoritmo: confronto ogni lettera della parola del dizionario con ciascuna lettera di lettereInput, cioè c con a, c con b, c con n, c con c -> trovato! ... modifico 'abnciay' in 'abniay ' e 'cabina' in 'abina'... Continuo così fino a che non ho finito le lettere della parola del dizionario; se così fosse significa che con le lettere di lettereInput posso creare quella parola.

abnciay -> c
cabina -> c

abniay -> a
abina -> a

bniay -> b
bina -> b

niay -> i
ina -> i

nay -> n
na -> n

ay -> a
a -> a

ho finito le lettere nella parola del dizionario, bene, con le lettere di lettereInput posso creare la parola 'cabina'.

Ora.. per implementare questo algoritmo devo cambiare nei vari for, ogni volta che trovo una corrispondenza, sia lettereInput, sia parolaDizionario (non saprei come fare), oppure implementare un'altro algoritmo....

qualche idea? Grazie


--- Ultima modifica di Robbizz in data 2019-07-16 00:54:05 ---

Allora, un po' di terminologia: quello che stai cercando di fare si chiama: anagramma (eventualmente con scarto) https://it.wikipedia.org/wiki/Anagramma. Un anagramma è un tipo di permutazione https://it.wikipedia.org/wiki/Permutazione


Ora, in python le permutazioni si fanno con itertools.permutations https://docs.python.org/3.7/library/itertools.html#itertools.permutations per cui nel tuo caso

>>> from itertools import permutations
>>> 'cabina' in [''.join(i) for i in permutations('abnciay', len('cabina')]
True

Oppure, meglio ancora perché evita la creazione di una lista di tutte le permutazioni:

>>> tuple('cabina') in permutations('abnciay', 6)
True

Un esempio di algoritmo per le permutazioni lo trovi nella documentazione di itertools.permutations sopra linkata.





Detto questo, ricorrere alle permutazioni per fare un anagramma può essere dispendioso. Un approccio più veloce sarebbe vedere se tutte le lettere della parola da cercare stanno nelle lettere di partenza. Se è così, allora l'anagramma si può fare senz'altro, è inutile mettersi a farlo davvero.


Ora, questo approccio sarebbe banale usando i set, se NON ci fossero mai lettere ripetute: esempio

>>> set('milano').issubset(set('ailmnoxyz')) # da 'ailmnoxyz' posso ricavare 'milano'
True

Perché i set, appunto, non ammettono ripetizioni. Siccome però noi ovviamente dobbiamo considerare il caso di lettere ripetute, la cosa più veloce che mi viene in mente sul momento è creare delle liste, ordinarle, e verificare se sono uguali:

>>> word = sorted(list('cabina'))
>>> letters = sorted([i for i in 'abnciay' if i in word]) # tolgo quelle che non stanno in 'cabina'
>>> word == letters
True

Ciao RicPol ... la risposta difatti me l'aspettavo proprio da te!
Il mio programmino (solo come esercizio, niente che vada in produzione) è quello in allegato... naturalmente incompleto e cercherò, tra le info che mi hai dato, di implementare l'algoritmo più performante. Il dizionario alla fine andrò a caricarlo da un file esterno con tutte o quasi i termi in italiano, così da provare la velocità di elaborazione....