3 ms·

If I understand the task correctly, it is to map a word into another word that belongs to the set of words that have the same letter frequency distribution. So

by bluefox 10y ago

If I understand the task correctly, it is to map a word into another word that belongs to the set of words that have the same letter frequency distribution. So a possible solution is to define a representation for a letter frequency distribution, and use an associative data type for the mapping. Since the problem does not concern itself with prefixes, there is no need for a prefix tree - in Python, a simple dict would do. A few words about style: when you write code, you have to come up with names for variables, functions, and other things. In this case, it seems you just went ahead and wrote down the first thing that came to mind, which is sometimes verbose because you're still in problem exploration mode and things are not clear. It's OK to do that, but please consider re-naming later on, so that instead of a first-thing-I-thought-of name, you'll have a name that gives the reader a sense of clarity. The process of doing that usually leads to better understanding of the problem and perhaps better code. With experience, you'll find that the need to re-name is reduced. As a rule of thumb, the length of the name should correlate with the its scope. Names with indefinite scope tend to be long, while names with limited scopes tend to be shorter. Finally, I encourage you to write more posts, and hope my critique is helpful.

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 ago
  Yes. 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 ago
  It 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.
ttub 10y ago
This problem also has an "infamous" and very simpe, elegant solution described in Programming Pearls: "The idea is to give words that are anagrams a common signature, sort all the words together by their signatures, and then print them." https://www.gnu.org/software/gawk/manual/html_node/Anagram-Program.html https://www.gnu.org/software/gawk/manual/html_node/Anagram-P...
thr0waway1239 10y ago
> Since the problem does not concern itself with prefixes, there is no need for a prefix tree This is a very important point, and many others in this thread have missed the fundamental point with using a trie. A real world example would immediately showcase its benefit. In the old feature phones, you needed to punch the number keys many times to get a letter. Some people improved this using something called predictive typing - which basically goes like this: 1. Each number can be mapped to one of 3-4 possible letters 2. Based on the current sequence of numbers typed in (i.e. the prefix up to this point), this can mean 0 or more words which are in the dictionary. 3. Using a trie data structure, you basically have a few possible leaf nodes (only dictionary words can be leaf nodes in the predictive typing scenario) which all map to the current sequence of numbers. 4. Hence you will notice one or more options from which you can select based on the number sequence you typed, thus saving you many keystrokes You can present the different options sorted by word frequency etc. if there are multiple matching leaf nodes for the given prefix. When the prefix scenario does not matter - as in OP's article, from what I remember the trie gives no benefit over a simple sorted dictionary.

by bluefox 10y ago

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 ago
Yes. 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 ago
It 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.

ttub 10y ago

This problem also has an "infamous" and very simpe, elegant solution described in Programming Pearls: "The idea is to give words that are anagrams a common signature, sort all the words together by their signatures, and then print them." https://www.gnu.org/software/gawk/manual/html_node/Anagram-Program.html https://www.gnu.org/software/gawk/manual/html_node/Anagram-P...

thr0waway1239 10y ago

> Since the problem does not concern itself with prefixes, there is no need for a prefix tree This is a very important point, and many others in this thread have missed the fundamental point with using a trie. A real world example would immediately showcase its benefit. In the old feature phones, you needed to punch the number keys many times to get a letter. Some people improved this using something called predictive typing - which basically goes like this: 1. Each number can be mapped to one of 3-4 possible letters 2. Based on the current sequence of numbers typed in (i.e. the prefix up to this point), this can mean 0 or more words which are in the dictionary. 3. Using a trie data structure, you basically have a few possible leaf nodes (only dictionary words can be leaf nodes in the predictive typing scenario) which all map to the current sequence of numbers. 4. Hence you will notice one or more options from which you can select based on the number sequence you typed, thus saving you many keystrokes You can present the different options sorted by word frequency etc. if there are multiple matching leaf nodes for the given prefix. When the prefix scenario does not matter - as in OP's article, from what I remember the trie gives no benefit over a simple sorted dictionary.