Hacker News Reader

> "Produce a dictionary of the number of times each letter occurs in each word." is heading the wrong direction. You want an encoding that does not care about the number of times each letter occurs in each word.

How so? "aab" is an anagram of "baa", but they are not anagrams of "ab".

100000 00000 00000 00000 00000 100000 00000 00000 00000 00000 010000 00000 00000 00000 00000

aab and baa

100000 00000 00000 00000 00000 010000 00000 00000 00000 00000 000000 00000 00000 00000 00000

ab

You aren't "counting" the number of characters. You're making an encoding that includes that information, without the aggregation. The aggregation is irrelevant as is the order of duplicate characters.

>which is (maxWordlength*26) long. Each segment of 26 represents a

>^We're going to assume normalized words, which are all lower case and no punctuation, comprised of English letters from the 26 character alphabet. Getting the set of all of the possible words of any given length, is also quite an exercise.

I hate solutions like this because they'd never be even close to being viable in real world

You could use a lookup table to turn the nth letter of the alphabet into the nth prime number, then multiply those primes together. This "hash" would be unique up to reordering of the primes/letters.

Sorry, I don't understand your comment. Why would the proposed "naive" solution of generating a dictionary not work in O(n) time? What is gained by this bit encoding?

And as far as I know, XAND does not exist?

What dictionary? How do you generate it (handwaving notwithstanding, as mentioned)? It all comes back down to encoding, rather than aggregation of letter count.^

> XAND does not exist?

XAND being a convenient way to mean binary AND. I thought it was easy to infer. Taking the binary encodings, you can do a binary AND to determine if a set is an anagram subset (or full anagram) with more flexibility.

^Create a hashmap (any searchable K/V will do, redis, postgres, etc). For each word, check to see if encoding exists in set. If not, add key of encoding and value of word. If it exists, you have a match on the search word and the found key's value. Aggregate on a hashmap there for your final output, to avoid adding the same words multiple times.

> What dictionary? How do you generate it (handwaving notwithstanding, as mentioned)? It all comes back down to encoding, rather than aggregation of letter count.^

OK, first, I'm not sure your original post presents the right reading of the blog post. Sorting and using a dictionary are given in the blog post as two separate solutions, not two components of one solution. (Sorry if I'm mistaken – but it seems to read this way to me?)

Regarding your concerns about dictionary generation: I might be missing something, but this doesn't seem so hard? The first thought that comes to mind is to associate to each word a 26-tuple of integers that counts the number of appearances of each letter of the alphabet. This can be done in O(N) time, since it's an O(1) operation for each word (length of words is assumed to be bounded above by some constant). Then

1) Create a (multi)-dictionary with these tuples as keys. Insert is O(1) in the average case, you're doing it N times, so this step is O(N).

2) Go through the dictionary by key and delete all singletons. Again O(N).

3) Print the dictionary by key to get the groups of anagrams.

This is O(N) on average. It's not immediately clear to me whether one can do O(N) in the worst case – are you claiming that your way does that?

[Of course, this is not so far off from what you're doing. But it illustrates the claim that bit arrays are not necessary.]

What is XAND?

exclusive and? Just guessing, I use some of these chips in my synthesizer