Given set of words, we need to find the anagram words and display each category alone using the best algorithm
input:
man car kile arc none like
output:
man
car arc
kile like
none
the best solution I am developing now is based on a hashtable, but I am thinking about equation to convert anagram word into integer value
exmaple: man => 'm'+'a'+'n' but this will not give unique values
any suggestions?
I don't think you'll find anything better than a hash table with a custom hash function (that would sort the letters of he word before hashing it).
Sum of the letters will never work, because you can't really make 'ac' and 'bb' different.
You will need large integers (or a bit vector actually) but the following might work
the first occurrence of each letter get's assigned the bit number for that letter, the second occurence gets the bit number for that letter + 26.
For example
a #1 = 1 b #1 = 2 c #1 = 4 a #2 = 2^26 b #2 = 2 ^ 27
You can then sum these together, to get a unique value for the word based on it's letters.
Your storage requirements for the word values will be:
n * 26 bits
where n is the maximum number of occurrences of any repeated letter.
Don't bother with a custom hash function at all. Use the normal string hash function on whatever your platform is. The important thing is to make the key for your hash table the idea of a "sorted word" - where the word is sorted by letter, so "car" => "acr". All anagrams will have the same "sorted word".
Just have a hash from "sorted word" to "list of words for that sorted word". In LINQ this is incredibly easy:
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);
}
}
Sample use:
c:\Users\Jon\Test>FindAnagrams.exe man car kile arc none like
man
car arc
kile like
none
see the following code in 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]));
}
}
the problem is how to develop GetUniqueInts(string []) method?
A Python version for giggles:
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())
I have implemented this before with a simple array of letter counts, e.g.:
unsigned char letter_frequency[26];
Then store that in a database table together with each word. Words that have the same letter frequency 'signature' are anagrams, and a simple SQL query then returns all anagrams of a word directly.
With some experimentation with a very large dictionary, I found no word that exceeded a frequency count of 9 for any letter, so the 'signature' can be represented as a string of numbers 0..9 (The size could be easily halved by packing into bytes as hex, and further reduced by binary encoding the number, but I didn't bother with any of this so far).
Here is a ruby function to compute the signature of a given word and store it into a Hash, while discarding duplicates. From the Hash I later build a SQL table:
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
I used a Godel-inspired scheme:
Assign the primes P_1 to P_26 to the letters (in any order, but to obtain smallish hash values best to give common letters small primes).
Built a histogram of the letters in the word.
Then the hash value is the product of each letter's associated prime raised to the power of its frequency. This gives a unique value to every anagram.
Python code:
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
This cleverly transforms the tricky problem of finding subanagrams into the (also known to be tricky) problem of factoring large numbers...
Assign a unique prime number to the letters a-z
Iterate your word array, creating a product of primes based on the letters in each word.
Store that product in your word list, with the corresponding word.
Sort the array, ascending by the product.
Iterate the array, doing a control break at every product change.
In C, I just implemented the following hash which basically does a 26-bit bitmask on whether the word in the dictionary has a particular letter in it. So, all anagrams have the same hash. The hash doesn't take into account repeated letters, so there will be some additional overloading, but it still manages to be faster than my perl implementation.
#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;
}
Overloaded buckets created and added as linked list, etc. Then just write a function that makes sure that the words that match the hash value are the same length and that the letters in each are 1 to 1 and return that as a match.
I will generate the hasmap based on the sample word and the rest of the alphabets I won't care.
For example if the word is "car" my hash table will be like this: a,0 b,MAX c,1 d,MAX e,MAX ... .. r,2 . As a result any has greater than 3 will consider as not matching
(more tuning...) And my comparison method will compare the hash total within the hash calculation itself. It won't continue once it can identify the word is not equal.
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;
}
Main method
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 + " ");
}
}