gila75 ha scritto: ↑giovedì 28 aprile 2022, 6:53
Grazie vae. Sono ancora limitate le mie conoscienze, ma mi pare di capire che si costruiscano due dizionari e poi si confrontino, ma devo vedere bene.
Avevo pensato anche agli insiemi, ma in casi particolari non funzionano.
Es: casa, casaa con i set mi da anagramma, ma non e' vero
A parte il motivo per cui coi set non funziona, giá spiegato, la logica é quella.
Prima ti calcoli per ogni parola il dizionario lettera/occorrenze per ogni lettera. Poi confronti che i dizionari siano uguali.
Da un punto di vista della complessitá, se le due parole contengono n ed m lettere rispettivamente, avrai O(n + m) per la creazione dei due dizionari. Ma considerando che si fa prima un controllo su queste lunghezze e se non sono uguali non si procede, si può presumenre che siano entrambe lunghe n. Quindi la complessità è O(N). Per il loro confronto, supponendo che il numero di lettere diverse nelle due parole sia rispettivamente k e l, avrai qualcosa dell'ordine di O(t) in cui t é il minore tra k ed l, perché in Python i dizionari hanno lookup di complessitá O(1) in quanto implementati (da non ricordo quale versione di Python) in termini di hash table.
Per calcolare il dizionario delle occorrenze, le cose si semplificano da un punto di vista di codice, che é anche piú pythonico, ma forse peggiorano in performance, se si usano i defaultdict della libreria collections:
Codice: Seleziona tutto
from collections import defaultdict
parola = "mississippi"
counter = defaultdict(int)
for letter in parola:
counter[letter] += 1
che é comunque analogo a
Codice: Seleziona tutto
counter = dict()
for letter in parola:
counter[letter] = counter.get(letter, 0) + 1
che é una versione piú compatta di quanto ho scritto nel mio precedente messaggio.
Sempre in collections, c'é Counter, con il quale puoi fare una cosa del tipo:
Codice: Seleziona tutto
def sono_anagrammi(prima_parola, seconda_parola):
from collections import Counter
return Counter(prima_parola) == Counter(seconda_parola)
(Appena ho tempo, torno sul discorso della complessitá)
p.s.: modifica il titolo con qualcosa di descrittivo, é abbastanza ovvio che se apri una discussione é per la soluzione di qualcosa. Specifica cosa: "funzione per controllo anagrammi"