There are some subtleties in this question that haven't been clarified yet.
However, I have a working prototype that seems to approximate what OP is asking for.
Before describing my approach, here is a test case.
For this test case, the word list is obtained from: http://www.cse.msu.edu/~cse231/PracticeOfComputingUsingPython/05_ListsTuples/Anagrams/3eslWordList.txt
(Disclaimer: search engine results may contain links to materials protected by copyright.)
The following filtering criteria are applied:
- Length at least 4
- All letters (no space, hyphen, apostrophes)
- All lower case (to skip the initialisms)
Then, each unique word is assigned an integer, starting from zero.
For each word, a small list of patterns are generated from it, by replacing one character with a placeholder each time. For example, from the word
care a list of 4 patterns would be generated:
Each pattern is then used to search the word list again. Unique hits are counted. Subtracting one from this number gives the number of friends for this word.
There are some other aspects which are merely performance optimizations. Since optimization is mostly a personal taste, I will skip the details unless there is a consensus that I should include them with my answer.
I also have C# source code, but I don't know if I should be posting them here or not, unless there is a consensus.
Of the C# classes, I would mention two for their particular usefulness:
- One is a bidirectional map between string and a sequentially assigned integer value (starting with zero). Essentially a
List<string> plus a
Dictionary<string, int> plus some logic.
- Another is a bidirectional multi-map between two set of integers from separate namespaces (Note). This is used to store tuples of
(wordIndex, patternIndex) and allow lookup using either one.
Tuple.Item1 means word index,
Tuple.Item2 means pattern index, and where the coincidence of a word index equal to a pattern index is completely inconsequential. (Please help me improve this description.)
First test case:
care should return 22 matches, itself included (therefore, 21 true friends)
care : 22
Second test case:
butter should return 10 matches, itself included (therefore, 9 true friends)
butter : 10