Metathesis pairs

Question

I've worked up a solution to this exercise from Think Python:

Exercise 3 Two words form a “metathesis pair” if you can transform one into the other by swapping two letters; for example, “converse” and “conserve”. Write a program that finds all of the metathesis pairs in the dictionary. Hint: don’t test all pairs of words, and don’t test all possible swaps. Solution: http://thinkpython2.com/code/metathesis.py. Credit: This exercise is inspired by an example at http://puzzlers.org.

I'm just looking for general feedback, as my solution differs from the given solution, thanks!

def make_words_list(input_filename):
    """
    Takes a text file, returns a list of words in that file.

    input_filename: text file

    returns: list
    """
    words_list = []
    with open(input_filename) as input_file:
        for line in input_file:
            word = line.split()[0]
            words_list.append(word)
    return words_list


def sorted_word(word):
    """
    Returns a string with characters rearranged in ASCII order.

    word: string

    returns: string
    """
    return ''.join(sorted(word))


def anagram_sets(wordlist):
    """
    Returns a dictionary with letter groups as strings, and anagrams of those
    strings as keys.

    wordlist: list

    returns: dict
    """
    anagram_dict = {}
    for word in wordlist:
        word_family = sorted_word(word)
        if word_family in anagram_dict:
            anagram_dict[word_family].append(word)
        else:
            anagram_dict[word_family] = [word]

    # Pare down dict to keys with more than one word (ie words with an anagram)
    for word_family, anagram_list in list(anagram_dict.items()):
        if len(anagram_list) < 2:
            del anagram_dict[word_family]
    return anagram_dict


def is_metathesis_pair(word1, word2):
    assert word1 != word2, "Words are the same word."
    assert len(word1) == len(word2), "Words are not equal in length."
    assert sorted_word(word1) == sorted_word(word2), (
            f"Words '{word1}', '{word2}' are not anagrams of eachother.")

    letter_pairs = zip(word1, word2)
    count = 0
    for letter_1, letter_2 in letter_pairs:
        if count > 2:
            return False
        if letter_1 != letter_2:
            count += 1
    if count == 2:
        return True
    elif count > 2:
        return False
    else:
        return "Error." 



def find_metathesis_pairs(anagram_dict):
    """
    Takes a dict mapping word families to words, and looks in each to find
    words that are metathesis pairs (ie words that are the same, except for a
    single pair of swapped letters.
    Returns a list of tuples of these pairs.

    anagram_dict: dict

    returns: list
    """
    metathesis_pairs_list = []
    for word_family in anagram_dict.keys():
        # Prevent iterating over a pair more than once by iterating over a word
        # and subsequent words in list.
        for word1_index in range(len(anagram_dict[word_family])):
            word1 = anagram_dict[word_family][word1_index]
            for word2 in anagram_dict[word_family][word1_index+1:]:
                if word1 != word2:
                    if is_metathesis_pair(word1, word2):
                        metathesis_pairs_list.append((word1, word2))
    return metathesis_pairs_list


def metathesis_pairs(input_filename):
    """
    Return list of metathesis pairs from a file (ie all pairs of words that
    differ by swapping two letters).

    input_filename: text file

    returns: list of tuples
    """
    wordlist = make_words_list(input_filename)
    anagram_dict = anagram_sets(wordlist)

    return find_metathesis_pairs(anagram_dict)

Answer 1

1. The code is well-documented and clear.

2. The docstring for make_words_list says

   returns a list of words in that file.
   

   but if you look carefully at the behaviour, what it does it return a list containing the first word on each line of the file:

   word = line.split()[0]
   

3. When you have a function like make_words_list that returns a list of results, it's often more convenient to generate the results one at a time using the yield statement. This means that if the results are also being consumed one at a time, then the whole list does not have to be kept in memory.

   So make_words_list could become:

   def read_words(filename):
       "Generate the first word on each line of the named file."
       with open(filename) as file:
           for line in file:
               yield line.split()[0]
   

   If the caller really does need a list, it is easy enough to call list:

   list(read_words(filename))
   

4. anagram_sets could be simplified using collections.defaultdict, like this:

   anagram_dict = defaultdict(list)
   for word in wordlist:
       anagram_dict[sorted_word(word)].append(word)
   

5. But actually it might be even better to use sets here rather than lists — this would ensure that no word could get added twice, and so you could avoid the test word1 != word2 later on.

   anagram_dict = defaultdict(set)
   for word in wordlist:
       anagram_dict[sorted_word(word)].add(word)
   

6. In anagram_dict you go to some trouble to remove words with no anagrams. But this is unnecessary — if you look at the logic in find_metathesis_pairs you'll see that nothing will go wrong if len(anagram_dict[word_family]) is 1. So it would be simpler to leave the dictionary alone.

7. is_metathesis_pair is missing a docstring.

8. is_metathesis_pair returns the string "Error" to indicate an error. It is risky to return an exceptional value like this to indicate an error, because the caller may forget to check for the exceptional value. And in fact this is what happened:

   if is_metathesis_pair(word1, word2):
   

   So in the error case, is_metathesis_pair returns the string "Error", but this treated the same as True by the if statement, and so the error gets ignored.

   It is better to raise an exception in exceptional cases.

9. is_metathesis_pair maintains a running count of mismatched letters in order to provide an early exit from the loop. But in practice we expect words to be short: in my computer's dictionary the average word length is just 10 letters. So we are not saving very much time by exiting early from the loop, and we are paying the cost of checking the count.

   So I think it would be better not to worry about the early exit, and just count all the mismatches:

   count = sum(l1 != l1 for l1, l2 in zip(word1, word2))
   

10. In find_metathesis_pairs there is a loop over the keys of a dictionary:

    for word_family in anagram_dict.keys():
    

    and then in the body of the loop the expression anagram_dict[word_family] occurs several times. When you have a loop like this it is better to loop over the keys and values simultaneous:

    for word_family, anagrams in anagram_dict.items():
    

    But if you do this, you'll see that you don't actually need word_family any more: it was only ever needed to look up the list of anagrams. So you might as well only loop over the values:

    for anagrams in anagram_dict.values():
    

11. There is a loop over all pairs of distinct words in each family:

    for word_family in anagram_dict.keys():
        for word1_index in range(len(anagram_dict[word_family])):
            word1 = anagram_dict[word_family][word1_index]
            for word2 in anagram_dict[word_family][word1_index+1:]:
    

    When you have a loop over distinct pairs, you can use itertools.combinations to combine the two loops into one:

    for anagrams in anagram_dict.values():
        for word1, word2 in combinations(anagrams, 2)
    

12. The changes I've suggested above have reduced the length of the code considerably. It might now make sense to inline some of the functions at their point of use. This results in the following:

    from collections import defaultdict
    from itertools import combinations
    
    def find_metathesis_pairs(words):
        "Generate the metathesis pairs in an iterable of words."
        families = defaultdict(set)
        for word in words:
            families[''.join(sorted(word))].add(word)
        for family in families.values():
            for pair in combinations(family, 2):
                if sum(l1 != l2 for l1, l2 in zip(*pair)) == 2:
                    yield pair
    

    Inlining functions doesn't always make sense, and you might legitimately prefer the version of the code with multiple small functions, but in this case I think joining them together makes the logic easier to follow.

Answer 2

You have a very well written piece of code. It is well documented, split into proper functions; can be followed through without needing any external help.

However, a few points to note:

for word_family, anagram_list in list(anagram_dict.items()):
    if len(anagram_list) < 2:
        del anagram_dict[word_family]

Here, you are calling list on an iterator. Python 3's dict.items() returns an iterator object, which can be used as is for your for loop operation. If you wrap it inside a list, it takes up the memory to store the whole list of items. As you don't need to actually have the whole list at any point, just go over them one-by-one.

for word_family, anagram_list in anagram_dict.items():
    if len(anagram_list) < 2:
        del anagram_dict[word_family]

---

Seeing the following:

if word1 != word2:

I do not think that the dictionary file might have duplicates, but if you think that they might, then instead of list, I'd suggest using set() which won't allow for duplicates.

for word_family, anagram_list in anagram_dict.items():
    if len(anagram_list) < 2:
        del anagram_dict[word_family]
    else:
        anagram_dict[word_family] = set(anagram_list)

---

for word_family in anagram_dict.keys():
    # Prevent iterating over a pair more than once by iterating over a word
    # and subsequent words in list.
    for word1_index in range(len(anagram_dict[word_family])):
        word1 = anagram_dict[word_family][word1_index]

I notice that you want to iterate over index and word of the anagram_dict values. I think you'll love the enumerate function (no need to compute length of list/set etc.)

for words_list in anagram_dict.values():
    # Prevent iterating over a pair more than once by iterating over a word
    # and subsequent words in list.
    for index, word1 in enumerate(words_list):
        for word2 in words_list[index+1:]:
            if word1 != word2:
                if is_metathesis_pair(word1, word2):
                    metathesis_pairs_list.append((word1, word2))

In the is_metathesis_pair check, the whole of following:

if count == 2:
    return True
elif count > 2:
    return False
else:
    return "Error." 

can be reduced to:

return count == 2

When you return "Error", it is a truthy value in Python, and your metathesis_pairs_list will get those words stored in it. You do not want that.

---

for letter_1, letter_2 in letter_pairs:
    if count > 2:
        return False
    if letter_1 != letter_2:
        count += 1

Changing the order of those if statements will save you one iteration when your counter goes from \$ 2 \$ to \$ 3 \$.

for letter_1, letter_2 in letter_pairs:
    if letter_1 != letter_2:
        count += 1
    if count > 2:
        return False