Algoritmo para agrupar palabras de anagrama

Question

Dado un conjunto de palabras, necesitamos encontrar las palabras del anagrama y mostrar cada categoría sola usando el mejor algoritmo.

de entrada:

man car kile arc none like 

de salida:

man 
car arc 
kile like 
none 

La mejor solución que estoy desarrollando ahora se basa en una tabla hash, pero estoy pensando en la ecuación para convertir la palabra en anagrama valor entero.

Ejemplo: man => 'm' + 'a' + 'n' pero esto no dará valores únicos.

¿Alguna sugerencia?

---

Ver siguiente código en C#:

string line = Console.ReadLine(); 
string []words=line.Split(' '); 
int[] numbers = GetUniqueInts(words); 
for (int i = 0; i < words.Length; i++) 
{ 
    if (table.ContainsKey(numbers[i])) 
    { 
     table[numbers[i]] = table[numbers[i]].Append(words[i]); 
    } 
    else 
    { 
     table.Add(numbers[i],new StringBuilder(words[i])); 
    } 

} 

El problema es cómo desarrollar GetUniqueInts(string []) método.

Answer 1

No se moleste con una función hash personalizada en absoluto. Usa la función hash de cadena normal en cualquier plataforma que tengas. Lo importante es hacer de la clave de su tabla hash la idea de una "palabra ordenada", donde la palabra se ordena por letras, por lo que "car" => "acr". Todos los anagramas tendrán la misma "palabra ordenada".

Simplemente tiene un hash de "palabra ordenada" a "lista de palabras para esa palabra ordenada".En LINQ esto es increíblemente fácil: el uso

using System; 
using System.Collections.Generic; 
using System.Linq; 

class FindAnagrams 
{ 
    static void Main(string[] args) 
    { 
     var lookup = args.ToLookup(word => SortLetters(word)); 

     foreach (var entry in lookup) 
     { 
      foreach (var word in entry) 
      { 
       Console.Write(word); 
       Console.Write(" "); 
      } 
      Console.WriteLine(); 
     } 
    } 

    static string SortLetters(string original) 
    { 
     char[] letters = original.ToCharArray(); 
     Array.Sort(letters); 
     return new string(letters); 
    } 
} 

muestra:

c:\Users\Jon\Test>FindAnagrams.exe man car kile arc none like 
man 
car arc 
kile like 
none 

Answer 2

No creo que encuentre nada mejor que una tabla hash con una función hash personalizada (que ordenaría las letras de la palabra antes de hash).

La suma de las letras nunca funcionará, porque no se puede hacer que 'ac' y 'bb' sean diferentes.

Answer 3

Tendrá grandes números enteros (o un vector de bits en realidad), pero el siguiente podría trabajar

la primera aparición de asignado el número de bits de cada letra del GET para esa letra, la segunda ocurrencia obtiene el número de bits para esa letra + 26.

Por ejemplo

un # 1 = 1 b # 1 = 2 C# 1 = 4 un # 2 = 2^26 b # 2 = 2^27

Puede sumarlos para obtener un valor único para la palabra en función de sus letras.

sus requisitos de almacenamiento de los valores de las palabras serán:

n * 26 bits

donde n es el número máximo de veces que aparece una letra repetida.

Answer 4

Una versión de Python para la risa:

from collections import defaultdict 
res = defaultdict(list) 
L = "car, acr, bat, tab, get, cat".split(", ") 

for w in L: 
    res["".join(sorted(w))].append(w) 

print(res.values()) 

Answer 5

He implementado esto antes con un simple array de cuentas de letras, por ejemplo:

unsigned char letter_frequency[26]; 

T lo almacena en una tabla de base de datos junto con cada palabra. Las palabras que tienen la misma 'firma' de frecuencia de letra son anagramas, y una simple consulta SQL luego devuelve todos los anagramas de una palabra directamente.

Con algunos experimentos con un diccionario muy grande, no encontré ninguna palabra que excediera un conteo de frecuencia de 9 para cualquier letra, por lo que la 'firma' se puede representar como una cadena de números 0,9 (El tamaño podría ser se redujo a la mitad fácilmente al empacar en bytes como hexadecimal, y se redujo aún más mediante la codificación binaria del número, pero hasta ahora no me he molestado en nada de esto).

Aquí hay una función de ruby ​​para calcular la firma de una palabra dada y almacenarla en una Hash, mientras descarta duplicados. A partir del hash que más adelante construir una tabla de SQL:

def processword(word, downcase) 
    word.chomp! 
    word.squeeze!(" ") 
    word.chomp!(" ") 
    if (downcase) 
    word.downcase! 
    end 
    if ($dict[word]==nil) 
    stdword=word.downcase 
    signature=$letters.collect {|letter| stdword.count(letter)} 
    signature.each do |cnt| 
     if (cnt>9) 
     puts "Signature overflow:#{word}|#{signature}|#{cnt}" 
     end 
    end 
    $dict[word]=[$wordid,signature] 
    $wordid=$wordid+1 
    end 
end 

Answer 6

que utiliza un esquema de inspiración Godel:

Asignar los números primos p_1 a P_26 a las letras (en cualquier orden, pero para obtener los valores de hash más bien pequeñas mejores para dar letras comunes primos pequeños).

Se ha creado un histograma de las letras de la palabra.

Luego, el valor hash es el producto de la prima asociada de cada letra elevada a la potencia de su frecuencia. Esto le da un valor único a cada anagrama. código

Python:

primes = [2, 41, 37, 47, 3, 67, 71, 23, 5, 101, 61, 17, 19, 13, 31, 43, 97, 29, 11, 7, 73, 83, 79, 89, 59, 53] 


def get_frequency_map(word): 
    map = {} 

    for letter in word: 
     map[letter] = map.get(letter, 0) + 1 

    return map 


def hash(word): 
    map = get_frequency_map(word) 
    product = 1 
    for letter in map.iterkeys(): 
     product = product * primes[ord(letter)-97] ** map.get(letter, 0) 
    return product 

Esto transforma anticipa al problema difícil de encontrar en el subanagrams (también conocido por ser complicado) problema de factorizar números grandes ...

Answer 7

Asignar un número primo única para las letras az

Iterar su matriz de palabras, creando un producto de números primos basado en las letras de cada palabra.
Almacene ese producto en su lista de palabras, con la palabra correspondiente.

Ordene la matriz, ascendiendo por el producto.

Iterar la matriz, haciendo un control break en cada cambio de producto.

Answer 8

En C, acabo de implementar el siguiente hash que básicamente hace una máscara de bits de 26 bits para saber si la palabra en el diccionario tiene una letra en particular. Entonces, todos los anagramas tienen el mismo hash. El hash no tiene en cuenta las letras repetidas, por lo que habrá una sobrecarga adicional, pero aún así es más rápido que mi implementación de Perl.

#define BUCKETS 49999 

struct bucket { 
    char *word; 
    struct bucket *next; 
}; 

static struct bucket hash_table[BUCKETS]; 

static unsigned int hash_word(char *word) 
{ 
    char *p = word; 
    unsigned int hash = 0; 

    while (*p) { 
     if (*p < 97 || *p > 122) { 
      return 0; 
     } 
     hash |= 2 << (*p - 97); 
     *p++; 
    } 

    return hash % BUCKETS; 
} 

Cubos sobrecargados creados y agregados como lista vinculada, etc.Luego, solo escriba una función que asegure que las palabras que coinciden con el valor hash tengan la misma longitud y que las letras en cada una sean 1 a 1 y devuélvalas como una coincidencia.

Answer 9

Generaré el hasmap basado en la palabra de muestra y el resto de los alfabetos no me importará.

Por ejemplo, si la palabra es "coche" mi tabla hash será así: a, 0 b, c MAX , 1 d, e MAX, MAX ... .. r, 2 . Como resultado cualquiera tiene más de 3 considerará que no coincide

(más ajuste ...) Y mi método de comparación comparará el total de hash dentro del cálculo de hash en sí. No continuará una vez que pueda identificar la palabra que no es igual.

public static HashMap<String, Integer> getHashMap(String word) { 
     HashMap<String, Integer> map = new HashMap<String, Integer>(); 
     String[] chars = word.split(""); 
     int index = 0; 
     for (String c : chars) { 
      map.put(c, index); 
      index++; 
     } 
     return map; 
    } 

    public static int alphaHash(String word, int base, 
      HashMap<String, Integer> map) { 
     String[] chars = word.split(""); 
     int result = 0; 
     for (String c : chars) { 
      if (c.length() <= 0 || c.equals(null)) { 
       continue; 
      } 
      int index = 0; 
      if (map.containsKey(c)) { 
       index = map.get(c); 
      } else { 
       index = Integer.MAX_VALUE; 
      } 
      result += index; 
      if (result > base) { 
       return result; 
      } 
     } 
     return result; 
    } 

método Main

HashMap<String, Integer> map = getHashMap(sample); 
     int sampleHash = alphaHash(sample, Integer.MAX_VALUE, map); 
     for (String s : args) { 
       if (sampleHash == alphaHash(s, sampleHash, map)) { 
        System.out.print(s + " "); 
       } 
      } 

Answer 10

yo no usaría hash ya que añade complejidad adicional para la consulta y se suma. El hashing, la clasificación y las multiplicaciones van a ser más lentos que una simple solución de histograma basada en arreglos con únicos de seguimiento. Peor caso es O (2n):

// structured for clarity 
static bool isAnagram(String s1, String s2) 
{ 
    int[] histogram = new int[256]; 

    int uniques = 0; 

    // scan first string 
    foreach (int c in s1) 
    { 
     // count occurrence 
     int count = ++histogram[c]; 

     // count uniques 
     if (count == 1) 
     { 
      ++uniques; 
     } 
    } 

    // scan second string 
    foreach (int c in s2) 
    { 
     // reverse count occurrence 
     int count = --histogram[c]; 

     // reverse count uniques 
     if (count == 0) 
     { 
      --uniques; 
     } 
     else if (count < 0) // trivial reject of longer strings or more occurrences 
     { 
      return false; 
     } 
    } 

    // final histogram unique count should be 0 
    return (uniques == 0); 
} 

Answer 11

anagramas se pueden encontrar en forma siguiente:

1. Longitud de palabra debe coincidir.
2. Realiza la adición de cada carácter en términos de valor entero. Esta suma coincidirá si realiza lo mismo en anagrama.
3. Realiza la multiplicación de cada carácter en términos de valor entero. El valor evaluado coincidirá si realiza lo mismo en anagrama.

Así que pensé en las tres validaciones anteriores, podemos encontrar anagramas. Corrígeme si estoy equivocado.

---

Ejemplo: abc cba

Longitud de ambas palabras es 3.

Suma de caracteres individuales para ambas palabras es 294.

Prod de caracteres individuales para ambas palabras es 941.094.

Answer 12

Versión de JavaScript. usando hash.

Tiempo Complejidad: 0 (nm), donde n es el número de palabras, m es la longitud de la palabra

var words = 'cat act mac tac ten cam net'.split(' '), 
    hashMap = {}; 

words.forEach(function(w){ 
    w = w.split('').sort().join(''); 
    hashMap[w] = (hashMap[w]|0) + 1; 
}); 

function print(obj,key){ 
    console.log(key, obj[key]); 
} 

Object.keys(hashMap).forEach(print.bind(null,hashMap)) 

Answer 13

Sólo quiero añadir solución pitón sencilla, además de las otras respuestas útiles:

def check_permutation_group(word_list): 
    result = {} 

    for word in word_list: 
     hash_arr_for_word = [0] * 128 # assuming standard ascii 

     for char in word: 
      char_int = ord(char) 
      hash_arr_for_word[char_int] += 1 

     hash_for_word = ''.join(str(item) for item in hash_arr_for_word) 

     if not result.get(hash_for_word, None): 
      result[str(hash_for_word)] = [word] 
     else: 
      result[str(hash_for_word)] += [word] 

return list(result.values()) 

código

Answer 14

pitón:

line = "man car kile arc none like" 
hmap = {} 
for w in line.split(): 
    ws = ''.join(sorted(w)) 
    try: 
    hmap[ws].append(w) 
    except KeyError: 
    hmap[ws] = [w] 

for i in hmap: 
    print hmap[i] 

de salida:

['car', 'arc'] 
['kile', 'like'] 
['none'] 
['man']