3 ms·
>So a possible solution is to define a representation for a letter frequency distribution, and use an associative data type for the mapping. out of curiosity,
by jedimastert 10y ago
>So a possible solution is to define a representation for a letter frequency distribution, and use an associative data type for the mapping.
out of curiosity, could one such representation just be all of the letters in the word, sorted? I wonder how the time-complexities would compare. I assume a trie would still be faster.
- bluefox 10y agoYes. Another simple representation if you assume a maximum number of occurrences per letter: (defvar *alphabet* "abcdefghijklmnopqrstuvwxyz") (defconstant capacity-in-bits 3) (defun key (word) (loop with key = 0 with max-occurrences = (1- (ash 1 capacity-in-bits)) for letter across *alphabet* for i upfrom 0 for occurrences = (count letter word) do (if (> occurrences max-occurrences) (error "too many occurrences") (setf (ldb (byte capacity-in-bits (* i capacity-in-bits)) key) occurrences)) finally (return key)))
- kornish 10y agoIt could be. Here's a python implementation: from collections import Counter freq_to_words = {} make_freq = lambda word: tuple(sorted(dict(Counter(word)).items())) with open('/usr/share/dict/words', 'r') as f: for line in f.read().split('\n'): freq = make_freq(line) if freq not in freq_to_words: freq_to_words[freq] = [] freq_to_words[freq].append(line) print freq_to_words[make_freq('gas')] # ['gas', 'sag'] For time complexities, this requires O(n) preprocessing but can do O(1) lookups, since it's a hash structure.