Gruppi Anagrammi

[hamming_burst]

Salve,

Ho questo problema, vorrei con il vostro aiuto formalizzare meglio ciò che pensavo, o sapere se può essere corretto.

Il problema è il seguente:

Un anagramma e una parola o frase ottenuta riarrangiando le lettere di un’altra parola o frase. Per esempio, ioccic e un anagrammadi ciccio. Senza spazi.
Si supponga di avere in input un vettore di $n$ stringhe di lunghezza massima $k$; si scriva un algoritmo che stampa in output tutte i gruppi di anagrammi contenuti in queste $n$ stringhe. Se ne discuta correttezza e complessità.

Esempio di input:
rosa
pippo
poppi
raso
orsa
giappone

Esempio di output:
rosa, raso, orsa
pippo, poppi

(Nota: non necessariamente devono comparire nello stesso ordine del file di input)

Quello che ho pensato:
Per ogni parola, misurarne la lunghezza, e riordinare/raggruppare il tutto per stringhe di lunghezza uguale.
Utilizzare il problema di "distanza di editing" modificando l'algoritmo di programmazione dinamica di string-matching k-approssimato. Nel problema k-approssimato si fa riferimento a procedure di "sostituzione", "inserimento" e "cancellazione".
Io ho pensato visto devo fare string-matching tra due parole di lunghezza uguale, visto che li ho raggruppati, il problema si riduce a vedere il solo numero di "sostituzioni" sia "<=lungezza stringa" e "inserimento"/cancellazione" = 0. Visto che un anagramma è fatto da solo spostamenti di lettere e non inserimenti/cancellazione di nuove.

questo è quanto ho prodottonel poco tempo che avevo. Vorrei sapere se è corretto e se sì, dove si può migliorare, basandosi su questa idea.

Ringrazio molto

[apatriarca]

Quello che farei io è inserire le stringhe in una mappa che ha come chiavi delle stringhe e come valori una lista di stringhe. Per ogni stringa, riordinerei i suoi caratteri e utilizzerei questa nuova stringa come chiave per l'inserimento nella mappa (ovviamente con inserimento nella mappa intendo dire l'inserimento nella lista corrispondente alla chiave). La complessità di questo algoritmo dipende da tantissimi fattori (in particolare l'implementazione scelta per la mappa e la lista e l'algoritmo usato per l'ordinamento delle stringhe).
Supponendo ad esempio di usare un algoritmo di ordinamento di complessità \(O(k \log k)\), un trie per la mappa e una semplice lista concatenata con l'inserimento in testa per la lista. Per ogni stringa dobbiamo riordinare la lista (\(O(k \log k)\), cercare la lista ordinata nel trie (\(O(k)\) e aggiungere la stringa nella lista (\(O(1)\)). Per cui alla fine la complessità del tutto dovrebbe essere qualcosa come \(O(n \, k \log k)\).

Immagino che si possa anche trovare il modo di stabilire se due stringhe sono anagrammi l'una dell'altra usando la distanza di editing, ma credo che sia più facile ed efficiente riordinare semplicemente le due stringhe in modo da avere un valore comune tra gli anagrammi da confrontare.

[hamming_burst]

"apatriarca":Quello che farei io è inserire le stringhe in una mappa che ha come chiavi delle stringhe e come valori una lista di stringhe. Per ogni stringa, riordinerei i suoi caratteri e utilizzerei questa nuova stringa come chiave per l'inserimento nella mappa (ovviamente con inserimento nella mappa intendo dire l'inserimento nella lista corrispondente alla chiave).

ah ecco, riordinarle le lettere. ma daiii....
Cercavo un modo per confrontare due parole, avevo pensato all'hash, ma $h(\text{stringa})!=h(\text{anagramma})$ riordinarle è n'idea. Si poteva anche "sommare" l'intero corrispondente.

La complessità di questo algoritmo dipende da tantissimi fattori (in particolare l'implementazione scelta per la mappa e la lista e l'algoritmo usato per l'ordinamento delle stringhe).
Supponendo ad esempio di usare un algoritmo di ordinamento di complessità \(O(k \log k)\), un trie per la mappa e una semplice lista concatenata con l'inserimento in testa per la lista. Per ogni st
ringa dobbiamo riordinare la lista (\(O(k \log k)\), cercare la lista ordinata nel trie (\(O(k)\) e aggiungere la stringa nella lista (\(O(1)\)). Per cui alla fine la complessità del tutto dovrebbe essere qualcosa come \(O(n \, k \log k)\).

io conoscevo l'albero dei suffissi, interessanti questi Trie

Immagino che si possa anche trovare il modo di stabilire se due stringhe sono anagrammi l'una dell'altra usando la distanza di editing, ma credo che sia più facile ed efficiente riordinare semplicemente le due stringhe in modo da avere un valore comune tra gli anagrammi da confrontare.

certo certo, ma in quel momento cercavo una maniera di confronto, e l'hash come l'avevo pensato non corrispondeva, perciò la distanza di editing era l'unica possibilità. Ti ringrazio molto

Però sarebbe interessante, secondo te che proprietà dovrebbe avere una distanza di editing per essere un'anagramma.
Ci penso su comunque.

Intanto grazie