Алгоритм группировки слов анаграммы - PullRequest
Новая
       84

Алгоритм группировки слов анаграммы

19 голосов
/ 28 декабря 2008

Учитывая набор слов, нам нужно найти слова анаграммы и отобразить каждую категорию отдельно, используя лучший алгоритм.

ввод: 

man car kile arc none like

выход: 

man
car arc
kile like
none

Лучшее решение, которое я сейчас разрабатываю, основано на хеш-таблице, но я думаю об уравнении для преобразования слова анаграммы в целочисленное значение.

Пример: man => 'm' + 'a' + 'n', но это не даст уникальных значений.

Есть предложения?

См. Следующий код в 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]));
    }

}

Проблема в том, как разработать GetUniqueInts(string []) метод.

Ответы [ 14 ]

0 голосов
/ 03 сентября 2013

версия JavaScript. используя хеширование.

Сложность времени: 0 (нм), где n - количество слов, m - длина слова 

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))
0 голосов
/ 27 февраля 2012

Анаграммы можно найти следующим образом:

  1. Длина слова должна совпадать.
  2. Выполнить сложение каждого символа в терминах целочисленных значений. Эта сумма будет соответствовать, если вы выполните то же самое на анаграмме.
  3. Выполнить умножение каждого символа в терминах целочисленных значений. Оцененное значение будет соответствовать, если вы выполните то же самое на анаграмме.

Итак, я продумал выше три подтверждения, мы можем найти анаграммы. Поправь меня, если я ошибаюсь.

Пример: abc cba

Длина обоих слов равна 3.

Сумма отдельных символов для обоих слов равна 294.

Количество отдельных символов для обоих слов составляет 941094.

0 голосов
/ 20 марта 2010

Я сгенерирую hasmap на основе примера слова и остальных алфавитов, которые меня не волнуют.

Например, если слово "машина" моя хеш-таблица будет выглядеть так: а, 0 б, MAX с, 1 д, MAX е, MAX ... .. г, 2 , В результате любой, имеющий больше 3, будет считаться не соответствующим

(больше настроек ...) И мой метод сравнения будет сравнивать сумму хеша в самом вычислении хеша. Он не будет продолжаться, если сможет определить, что слово не равно. 

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

Основной метод 

  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 + " ");
                }
            }
0 голосов
/ 12 августа 2009

В C я только что реализовал следующий хеш, который в основном выполняет 26-битную битовую маску на предмет того, содержит ли слово в словаре определенную букву. Итак, все анаграммы имеют одинаковый хэш. Хеш не учитывает повторяющиеся буквы, поэтому будет некоторая дополнительная перегрузка, но все же он будет быстрее, чем моя реализация 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;
}

Перегруженные сегменты создаются и добавляются в виде связанного списка и т. Д. Затем просто напишите функцию, которая гарантирует, что слова, соответствующие значению хеш-функции, имеют одинаковую длину, и что буквы в каждом из них имеют значения от 1 до 1, и возвращают их как соответствующие .

Страница:
...