사전에서 anagram의 목록을 얻으십시오

Question

기본적으로 Anagrams는 문자열의 순열과 같습니다. stack, sackt, stakc 모두는 stack의 anagrams입니다 (위의 단어는 의미가 없다고 생각됩니다). 어쨌든 당신은 내가 기본적으로 의미하는 것을 이해할 수있었습니다.

지금은 anagrams 개의 단어가 나열되어 있거나 단순히 사전에서 말하고 싶습니다.

내 기본적인 질문은 정렬하고 시간 복잡도의로 작동하지 않습니다 비교하는 아주 나쁜 Find total number of unique anagrams in a dictionary?

입니다.

해시 테이블, 문자열을 키로 생각했습니다.

하지만 문제는 해시 함수가되어야한다는 것입니다. 일부 의사 코드 이 제공된 경우 도움이됩니다. 언급 된 접근법보다 나은 다른 접근법이 도움이 될 것입니다.

감사합니다.

Answer 1

명백한 해결책은 각 문자를 소수에 매핑하고 소수를 곱하는 것입니다. > 2 'B'- -> 3 다음

• 'AB'-> 6
• 'BA'-> 6
• "BAB '-> 18
그래서'A ''만약
• '아바'-> 36
• '바바'- 오버 플로우의 가능성을 최소화하기> 36

가 작은 소수가 더 자주 문자 (할당 될 수있다 즉, t, I, A, N). 참고 : 26 번째 소수는 101입니다.

UPDATE : an implementation can be found here

Answer 2

가능한 해시 함수 중 하나는 각 문자의 발생 횟수를 정렬 한 횟수 (영어로만 가정) 일 수 있습니다. 그래서 "anagram"은 [('a', 3), ('g', 1), ('n', 1), ('m', 1), ('r', 1)]을 생성합니다.

또는 단어에서 비트 마스크를 생성하여 부정확 한 그룹화를 얻을 수 있습니다. 여기서 비트 0-25는 각 비트가 해당 문자의 유무를 나타냅니다 (비트 0은 'a'부터 비트 25까지 'z'를 나타냄). . 하지만 각 해시 그룹을 더 구분하여 처리하는 데 더 많은 처리를해야합니다. "to"에서 "too"까지.

이러한 아이디어 중 하나가 도움이됩니까? 마음에 든 특정 구현 언어 (C++, Python 또는 Scala를 할 수 있습니까?)

편집 : 몇 가지 예제 스칼라 코드와 출력을 추가 :

OK : 나는 순간 스칼라 모드에서, 그래서 내가 물어하지만 (에헴) 무엇을 할 수있는 뭔가 위로를 노크 한을 스칼라 또는 함수형 프로그래밍에 익숙하지 않다면 명확하지 않을 수 있습니다. 여기에서 영어 단어의 큰 목록 사용

: 나는 그들에이 스칼라 코드를 실행 http://scrapmaker.com/data/wordlists/twelve-dicts/2of12.txt

(약 40,000 단어의 사전과, 컴파일을 포함하여, 스크립트 모드에서 시간을 스칼라 2.9을 사용하여 약 5 초 정도 소요 가장 효율적인 코드는 아니지만 가장 먼저 떠오르는 코드). 이 첫 번째 제안을 사용하는

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) 

주 (문자 카운트의 목록)하지 :

// 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 개 세트를 덤프 보다 복잡한 비트 마스크 방법.

편집 2 : 당신은 (JAB에 의해 제안) 각 단어의 문자에 대한 간단한 분류와 해쉬 함수를 교체하고 명확하게/빠른 코드와 같은 결과를 얻을 수 있습니다 :

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

Answer 3

시간 복잡성이 매우 심하기 때문에 정렬 및 비교가 작동하지 않습니다.

단지 26- char (또는 사용, 당신을 가정하고 어떤 언어로 상당의 단어에서 문자의 수를 저장하는 로마 알파벳을 사용하고 있고, 추가 메모리에 대한 시간 복잡도를 교환 알파벳 문자 만) 배열을 배열 해시합니다. 단어 길이에 비해 O (n) 시간이 붙어 있지만 대부분의 영어 단어는 그다지 길지 않습니다.

stack, sackt 및 stakc 모두의 위치와 배열을 것 s, t이 a이 c가 k == 1, 나머지 모든 설정을 의미 귀하의 의견에 기초

---

0으로 당신은 단어 자체를 정렬하지 않는 한 실제로 단어의 문자를 정렬하는 것이 옳습니다. Alex의 대답보다 단순한 작업을 수행하고 단어 문자열의 문자를 정렬하고 결과를 해시 할 수 있습니다. (larsmans가 먼저 말했지만 대답으로 게시하지 않았습니다 ...)

Answer 4

각 문자의 해시 코드 값을 XOR 한 다음 결과를 입력 길이만큼 XOR하면 단어의 순서에 관계없이 동일한 값, 즉 모든 애너그램이 동일한 해시를 생성한다는 것을 의미합니다.

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

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

    return output^input.Length; 
} 

당신은 여전히 ​​것입니다 :

예 (자체에 대한 'S'의 해시는 항상 0이기 때문에 길이로 XOR 연산은 같은 값을 반환에서 '보스'와 '보'를 방지) 동일한 AnagramHash로 모든 단어를 검색해야합니다. 전체 계산을 줄이기 위해 알고리즘에 관계없이 해시 필드를 사용하여 사전 테이블을 업데이트합니다.

EDIT : 또한 XOR은 ALU가 수행하는 가장 간단한 연산이므로 사용을 끝내면 상당히 빠르게 해시를 생성 할 수 있습니다.

Answer 5

문자열 목록은 주요 캐릭터의 모든 철자 바꾸기를 포함하는 값으로 키 목록 (문자열)와 같은 문자열을 해시 맵을 사용합니다.

문제는

보기 너 한테 여기 코드 http://justprogrammng.blogspot.com/2012/06/determine-anagrams-of-word-in-file.html