A Nice Application of Reduce and Set Theory

Today I want to give an example of a situation where understanding what’s going on at a combinatorial level can yield a very nice solution.

Spefically, I want to look at Leetcode problem 17. It’s pretty simple:

Let the letters of the alphabet map to numbers via the telephone keypad. In case you don’t have a phone handy, the map looks like this:

abc  -> 2
def  -> 3
ghi  -> 4
jkl  -> 5
mno  -> 6
pqrs -> 7
tuv  -> 8
wxyz -> 9

We’re given a sequence of digits, and we are told to reconstruct every possible sequence of letters that could have yielded this seqeuence of digits.

Here’s the example given:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

The most intuitive way to do this, and the way most people do it, is to have a recursive function drill down into the tree of combinations. Something like this would do it:

class Solution:
    def letterCombinations(self, digits):  
        if not digits:
            return []
        
        f = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'}   
        
        combos = []
        def build_combos(digits, comb=''):
            if not digits:
                combos.append(comb)
                return 
            for c in f[digits[0]]:
                build_combos(digits[1:], comb+c) 
        build_combos(digits)
        return combos

Now this is fine and all, but it’s not totally foolproof. It would be pretty easy to introduce an off-by-one error, or generate total nonsense if you recursed on a mutable list, instead of an immutable string.

Let’s take a step back and look at it another way.

The example given is instructive. It’s basically two steps:

2, 3 -> "abc", "def"
"abc", "def" -> "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"

The first step is pretty clear, but what’s going on in the second step?

Let’s define set A to contain the letters a, b, and c, and define set B to contain the letters d, e, and f. The second step takes each element of A, and appends each element of B to form an ordered pair. In procedural code, this would look like a nested for-loop:

combos = []
for a in A:
    for b in B:
        combos.append(a+b)

Turns out there’s a word for this concept, since it appears so often. It’s called a Cartesian product, and it’s denoted, for sets A and B, as A x B.

So for this example, we could get away with writing a function to compute the Cartesian product of the two sets of letters:

def cart(A, B):
   return [a+b for a in A for b in B]

(A more general cart function would allow us to pass in a function that dictated how the elements were to be combined, but since we’re just concatenating strings, this will do.)

A simple call to cart('abc', 'def') would give us all we need.

But that’s not good enough, because we need to be able to handle an arbitrary number of digits. How can we extend this to the three-digit case?

Well, maybe you see where this is going. Lets say our third digit is 4, which maps to g, h and i, which we’ll say constitute set C. We’re going to take each element of the set we just generated, and tack on each element of C. Sounds awful similar to what we did before. In fact, in our product notation, it’s exactly this: (A x B) x C.

We already have a function that generates the Cartesian product, we just need to apply it twice. How can we extend this to an arbitrary number of sets?

Enter reduce. Reduce takes two arguments: a function that takes two arguments, and an iterable. We use it like this:

from functools import reduce

def cart(A, B):
   return [a+b for a in A for b in B]

A, B, C = 'abc', 'def', 'ghi'
combos = reduce(cart, [A, B, C])

And that’s all we need. In the above case, calling reduce(cart, [A, B, C]) is equivalent to calling cart(cart(A, B), C). What you’re looking at is the beauty of induction, which basically says that if you know how the simplest case works, and you know how to get from a case of length n to a case of length n+1, then you’re done.

Here’s the final solution:

from functools import reduce

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        
        f = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'}
        f = {k: list(v) for k,v in f.items()}
        
        def cart(A, B):
            return [a + b for a in A for b in B]
        
        digit_letters = map(lambda x: f[x], digits)
        combs = reduce(cart, digit_letters) 
        return combs

As an added bonus to the conceptual clarity and lower risk of bugs, this code is performant, since the Python interpreter can easily optimize list comprehensions.

Jan 30, 2019