Вопрос по hash, anagram, data-structures – получить список анаграмм из словаря
==============================================================================

По сути, анаграммы подобны перестановке строк. Например,`stack` ,`sackt` ,`stakc` все анаграммы`stack` (мысли выше слова не имеют смысла). В любом случае вы могли бы понять, что я имел в виду.

Теперь я хочу список`anagrams` дали миллион слов или просто сказали из словаря.

Мой основной вопрос`Find total number of unique anagrams in a dictionary?`

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

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

Но проблема в том, какой должна быть хеш-функция? Было бы полезно, если какой-нибудь псевдокод
предоставлена. Некоторые другие подходы лучше упомянутых подходов также будут полезны.

Благодарю.

их слов) отсортированный счетчик числа вхождений каждой буквы. Так что для "анаграммы" вы бы сгенерировали [('a', 3), ('g', 1), ('n', 1), ('m', 1), ('r', 1)].

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

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

**Edit: added some example Scala code and output:**

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

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

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

```
// 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)

```

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

**Edit 2: You can replace the hash function with a simple sort on the chars of each word (as suggested by JAB) and get the same result with clearer/faster code:**

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

```



ь простые числа. Так что, если "a"; " - & GT; 2 и 'b' - & GT; 3, то

'ab' -> 6
'ba' -> 6
'bab' -> 18
'abba' -> 36
'baba' -> 36
Чтобы минимизировать вероятность переполнения, наименьшие простые числа могут быть назначены более частым буквам (e, t, i, a, n). Примечание: 26-е простое число - 101.

ОБНОВИТЬ:
[реализацию можно найти здесь](https://stackoverflow.com/a/14739948/905902)



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

Пример:

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

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



t work as it's time complexity is pretty bad.

Обменивая временную сложность на дополнительную память, просто сохраняйте количество букв в слове в 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](https://justprogrammng.blogspot.com/2012/06/determine-anagrams-of-word-in-file.html)