Tutti anagrammi in un file

Question

Fonte: Domanda Di Intervista Microsoft

ci viene dato un file contenente words.We bisogno di determinare tutte le Anagrammi in esso presenti.

Qualcuno può suggerire l'algoritmo più ottimale per farlo.

L'unico modo che conosco è Ordinamento di tutte le parole, quindi controllo.

Answer 1

Sarebbe bello sapere di più sui dati prima di suggerire un algoritmo, ma lascia supporre che le parole siano in inglese nel singolo caso.

Consente di assegnare a ciascuna lettera un numero primo compreso tra 2 e 101. Per ogni parola è possibile contare il suo "numero anagramma" moltiplicando i numeri corrispondenti della lettera.

Consente di dichiarare un dizionario di {numero, elenco} coppie. E una lista per raccogliere gli anagrammi risultanti in.

Quindi possiamo raccogliere anagrammi in due passaggi: basta attraversare il file e inserire ogni parola in un elenco di dizionari in base al suo "numero anagramma"; traverce la mappa e per ogni coppia di elenchi di lunghezza più di 1 memorizza i contenuti in un'unica grande lista di anagrammi.

UPDATE:

import operator 

words = ["thore", "ganamar", "notanagram", "anagram", "other"] 

letter_code = {'a':2, 'b':3, 'c':5, 'd':7, 'e':11, 'f':13, 'g':17, 'h':19, 'i':23, 'j':29, 'k':31, 'l':37, 'm':41, 'n':43, 
      'o':47, 'p':53, 'q':59, 'r':61, 's':67, 't':71, 'u':73, 'v':79, 'w':83, 'x':89, 'y':97, 'z':101} 

def evaluate(word): 
    return reduce(operator.mul, [letter_code[letter] for letter in word]) 

anagram_map = {} 
anagram_list = [] 
for word in words: 
    anagram_number = evaluate(word) 
    if anagram_number in anagram_map: 
     anagram_map[ anagram_number ] += [word] 
    else: 
     anagram_map[ anagram_number ] = [word] 

    if len(anagram_map[ anagram_number ]) == 2: 
     anagram_list += anagram_map[ anagram_number ] 
    elif len(anagram_map[ anagram_number ]) > 2: 
     anagram_list += [ word ] 

print anagram_list 

Naturalmente l'applicazione può essere ottimizzato ulteriormente. Ad esempio, non hai davvero bisogno di una mappa di anagrammi, solo un contatore andrebbe bene. Ma immagino che il codice mostri l'idea migliore così com'è.

Answer 2

È possibile utilizzare "Cerca". Un trie (derivato dal recupero) è un albero di ricerca a più vie. Tries utilizza algoritmi di corrispondenza dei modelli. L'uso di base è quello di creare programmi di controllo ortografico, ma penso che possa aiutare il tuo caso .. Date un'occhiata a questo link http://ww0.java4.datastructures.net/handouts/Tries.pdf

Answer 3

Ho appena fatto questo non molto tempo fa, in un modo diverso.

1. dividere il contenuto del file in un array di parole
2. creare un HashMap che mappa una stringa chiave per una lista concatenata di stringhe
3. per ogni parola nella matrice, ordinare le lettere della parola e l'uso che come la chiave per una lista concatenata di anagrammi

public static void allAnagrams2 (String s) { String [] input = s.toLowerCase(). replaceAll ("[^ az^\ s]", " ").divide"); HashMap> hm = new HashMap>();

for (int i = 0; i < input.length; i++) { 
     String current = input[i]; 

     char[] chars = current.toCharArray(); 
     Arrays.sort(chars); 
     String key = new String(chars); 

     LinkedList<String> ll = hm.containsKey(key) ? hm.get(key) : new LinkedList<String>(); 
     ll.add(current); 

     if (!hm.containsKey(key)) 
      hm.put(key, ll); 
    } 
} 

Answer 4

Un approccio leggermente diverso da quello sopra. Invece di restituire una Hashmap di anagrammi.

Public static Hashmap<String> anagrams(String [] list){ 

    Hashmap<String, String> hm = new Hashmap<String, String>(); 
    Hashmap<String> anagrams = new Hashmap<String>(); 

    for (int i=0;i<list.length;i++){ 
     char[] chars = list[i].toCharArray(); 
     Arrays.sort(chars); 
     String k = chars.toString(); 
     if(hm.containsKey(k)){ 
      anagrams.put(k); 
      anagrams.put(hm.get(k)); 
     }else{ 
      hm.put(k, list[i]); 
     } 
    } 
}