algorithm - mismas - Algoritmo para agrupar palabras de anagrama

los mejores anagramas

Question

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

entrada:

man car kile arc none like

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 anagrama en un valor entero.

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

¿Cualquier sugerencia?

Ver el 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 el GetUniqueInts(string []) .

Answer 1

Asignar un número primo único a las letras az

Iterate tu matriz de palabras, creando un producto de 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 corte de control en cada cambio de producto.

Answer 2

Lo he implementado antes con una simple serie de recuentos de letras, por ejemplo:

unsigned char letter_frequency[26];

Luego, almacénelo 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 ninguna letra, por lo que la ''firma'' se puede representar como una cadena de números 0,9 (el tamaño podría ser reducido a la mitad fácilmente mediante el embalaje en bytes como hexadecimal, y reducido aún más por codificación binaria del número, pero no me molesté con nada de esto hasta ahora).

Aquí hay una función Ruby para calcular la firma de una palabra dada y almacenarla en una Hash, mientras descarta duplicados. Desde Hash, luego construyo una tabla 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 3

Necesitará enteros grandes (o un vector de bits en realidad) pero podría funcionar lo siguiente

a la primera aparición de cada letra se le asigna el número de bit para esa letra, la segunda ocurrencia obtiene el número de bit para esa letra + 26.

Por ejemplo

a # 1 = 1 b # 1 = 2 c # 1 = 4 a # 2 = 2 ^ 26 b # 2 = 2 ^ 27

A continuación, puede sumarlos para obtener un valor único para la palabra en función de sus letras.

Sus requisitos de almacenamiento para los valores de palabra serán:

n * 26 bits

donde n es el número máximo de ocurrencias de cualquier letra repetida.

Answer 4

No creo que encuentres 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 puedes hacer que ''ac'' y ''bb'' sean diferentes.

Answer 5

No te molestes 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".

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

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);
    }
}

Uso de muestra:

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

Answer 6

Una versión de Python para risas:

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 7

Usé un esquema inspirado en Godel:

Asigne los números primos P_1 a P_26 a las letras (en cualquier orden, pero para obtener valores pequeños de hash, mejor para dar a las letras comunes primos pequeños).

Construyó un histograma de las letras en la palabra.

Entonces 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 de 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 inteligentemente transforma el difícil problema de encontrar subanagramas en el problema (también conocido por ser complicado) de factorizar grandes números ...

Answer 8

En C, acabo de implementar el siguiente hash, que básicamente hace una máscara de bits de 26 bits sobre 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 "auto", mi tabla hash será así: a, 0 b, MAX c, 1 d, MAX e, MAX ... .. r, 2. Como resultado, cualquier que tenga 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. 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 principal

  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

No utilizaría hashing ya que agrega complejidad adicional para búsqueda y agrega. El hash, 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. El 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

Los anagramas se pueden encontrar de la siguiente manera:

1. La longitud de la palabra debe coincidir.
2. Realice 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

La longitud de ambas palabras es 3.

La suma de los caracteres individuales para ambas palabras es 294.

Prod de caracteres individuales para ambas palabras es 941094.

Answer 12

Versión de JavaScript usando hash.

Complejidad del tiempo: 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

Solo quiero agregar una solución simple de Python además de 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())