получить список анаграмм из словаря

Очевидное решение состоит в том, чтобы сопоставить каждый символ с простым числом и умножить простые числа. Итак, если «а» -> 2 и «б» -> 3, то

• 'ab' -> 6
• 'ba' -> 6
• 'баб' -> 18
• 'абба' -> 36
• 'баба' -> 36

Чтобы свести к минимуму вероятность переполнения, наименьшие простые числа можно было присвоить более часто встречающимся буквам (e, t, i, a, n). Примечание: 26-е простое число равно 101.

ОБНОВЛЕНИЕ: здесь можно найти реализацию

Одной из возможных хэш-функций может быть (предполагая только английские слова) отсортированный подсчет количества вхождений каждой буквы. Таким образом, для «анаграммы» вы должны сгенерировать [('a', 3), ('g', 1), ('n', 1), ('m', 1), ('r', 1)].

В качестве альтернативы вы можете получить неточную группировку, сгенерировав битовую маску из вашего слова, где для битов 0-25 каждый бит представляет наличие или отсутствие этой буквы (от бита 0, представляющего «а», до бита 25, представляющего «z»). Но тогда вам придется выполнить немного больше обработки, чтобы разделить каждую хешированную группу, чтобы различать, например. «к» от «тоже».

Любая из этих идей помогает? Какой-то конкретный язык реализации (я мог бы сделать C++, python или Scala)?

Редактировать: добавлен пример кода Scala и вывод:

ОК: В данный момент я нахожусь в режиме Scala, поэтому я кое-что придумал, чтобы сделать то, что вы просите, но (кхм) это может быть не очень понятно, если вы не знакомы со Scala или функциональным программированием.

Используя большой список английских слов отсюда: http://scrapmaker.com/data/wordlists/twelve-dicts/2of12.txt

Я запускаю на них этот код Scala (занимает около 5 секунд, используя Scala 2.9 в режиме скрипта, включая время на компиляцию, со словарем около 40 000 слов. Не самый эффективный код, но первое, что пришло в голову).

// Hashing function to go from a word to a sorted list of letter counts
def toHash(b:String) = b.groupBy(x=>x).map(v => (v._1, v._2.size) ).toList.sortWith(_._1 < _._1)


// Read all words from file, one word per line
val lines = scala.io.Source.fromFile("2of12.txt").getLines

// Go from list of words to list of (hashed word, word)
val hashed = lines.map( l => (toHash(l), l) ).toList

// Group all the words by hash (hence group all anagrams together)
val grouped = hashed.groupBy( x => x._1 ).map( els => (els._1, els._2.map(_._2)) )

// Sort the resultant anagram sets so the largest come first
val sorted = grouped.toList.sortWith( _._2.size > _._2.size )

for ( set <- sorted.slice(0, 10) )
{
    println( set._2 )
}

Это выводит первые 10 наборов анаграмм (сначала наборы с наибольшим количеством членов):

List(caret, cater, crate, react, trace)
List(reins, resin, rinse, risen, siren)
List(luster, result, rustle, sutler, ulster)
List(astir, sitar, stair, stria, tarsi)
List(latrine, ratline, reliant, retinal)
List(caper, crape, pacer, recap)
List(merit, miter, remit, timer)
List(notes, onset, steno, stone)
List(lair, liar, lira, rail)
List(drawer, redraw, reward, warder)

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

Редактирование 2. Вы можете заменить хеш-функцию простой сортировкой символов каждого слова (как предлагает JAB) и получить тот же результат с более четким/быстрым кодом:

def toHash(b:String) = b.toList.sortWith(_<_)

Если вы выполняете операцию XOR над значениями хэш-кода каждого символа, а затем выполняете операцию XOR над результатом по длине ввода, вы получите одно и то же значение независимо от порядка слов, а это означает, что все анаграммы будут давать один и тот же хэш. (Исключающее ИЛИ по длине не позволяет 'boss' и 'bo' возвращать одно и то же значение, потому что хэш 's' против самого себя всегда равен 0.)

Пример:

int AnagramHash(string input)
{
    int output = 0;

    foreach(char c in input)
        output ^= c.GetHashCode();

    return output ^ input.Length;
}

Вам все равно придется искать все слова с одним и тем же AnagramHash. Я бы обновил таблицу словаря полем для хеша (независимо от вашего алгоритма), чтобы сократить общие вычисления.

РЕДАКТИРОВАТЬ: Кроме того, в качестве примечания, XOR — это самая простая операция, выполняемая ALU, поэтому, если вы в конечном итоге используете ее, вы сможете довольно быстро генерировать свои хэши.

Сортировка и сравнение не будут работать, так как временная сложность довольно плохая.

Обменяв временную сложность на дополнительную память, просто сохраните количество букв в слове в массиве 26-char (или эквиваленте на любом языке, который вы используете, и предполагая, что вы используете латинский алфавит и только буквенные символы) и хешировать массив. Вы застряли со временем O(n) относительно длины слова, но большинство английских слов на самом деле не такие длинные.

например stack, sackt и stakc все будут иметь массив с местоположениями для s, t, a, c, k == 1, а все остальные будут установлены в 0.

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

Используйте хэш-карту со строкой в ​​качестве ключа и списком (строка) в качестве значения, где список строк содержит все анаграммы ключевой строки.

Вопрос похож на "найти все анаграммы слова в файле"

Посмотреть алгоритм и код можно здесь http://justprogrammng.blogspot.com/2012/06/determine-anagrams-of-word-in-file.html