Given two or more lists, like [1, 2] and [3, 4], the Cartesian product of those lists contains all ordered combinations of the elements within those lists: [1, 3], [1, 4], [2, 3], and [2, 4]. This may not seem like much, but Cartesian products are an algorithmic superpower. Maybe it’s J’s subtle influence over my programming style, but I find myself reaching more and more for Cartesian products in the algorithms I write, and I’m constantly awed by the simplicity and clarity the bring to my solutions.

As an example of how useful they can be, let’s look at the problem of generating all possible guitar chord voicings, like I do in Glorious Voice Leader. As a quick aside, if you want to know more about Glorious Voice Leader, check out last week’s post!

Imagine we’re trying to generate all possible C major chord voicings across a guitar’s fretboard. That is, we’re trying to find all playable combinations of the notes C, E, and G. How would we do this?

One approach, as you’ve probably guessed, is to use Cartesian products!

Let’s assume that we have a function, findNoteOnFretboard, that gives us all the locations (zero-based string/fret pairs) of a given note across the fretboard. For example, if we pass it a C (0 for our purposes), we’ll receive an array of string/fret pairs pointing to every C note on the fretboard:

[[0,8],[1,3],[1,15],[2,10],[3,5],[3,17],[4,1],[4,13],[5,8]]

Plotted on an actual guitar fretboard, we’d see all of our C notes exactly where we’d expect them to be:

Now imagine we’ve done this for each of our notes, C, E, and G:

let cs = findNoteOnFretboard(frets, strings, tuning)(0);
let es = findNoteOnFretboard(frets, strings, tuning)(4);
let gs = findNoteOnFretboard(frets, strings, tuning)(7);

The set of all possible voicings of our C major chord, or voicings that contain one of each of our C, E, and G notes, is just the cartesian product of our cs, es, and gs lists!

let voicings = _.product(cs, es, gs);

We’re using the lodash.product here, rather than going through the process of writing our own Cartesian product generator.

We can even generalize this to any given array of notes, and wrap it up in a function:

const voicings = (
  notes,
  tuning = [40, 45, 50, 55, 59, 64],
  frets = 18,
  strings = _.size(tuning)
) =>
  _.chain(notes)
    .map(findNoteOnFretboard(frets, strings, tuning))
    .thru(notesOnFretboard => _.product(...notesOnFretboard))
    .value();

Finding Notes on the Fretboard

So that’s great and all, but how do we implement our findNoteOnFretboard function? With Cartesian products, of course! We’ll generate a list of every string and fret position on the fretboard by computing the Cartesian product of each of our possible string and fret values:

const findNoteOnFretboard = (frets, strings, tuning) => note =>
  _.chain(_.product(_.range(strings), _.range(frets)))
    .value();

Next, we’ll need to filter down to just the string/fret pairs that point to the specified note:

const isNote = (note, tuning) => ([string, fret]) =>
  (tuning[string] + fret) % 12 === note;

const findNoteOnFretboard = (frets, strings, tuning) => note =>
  _.chain(_.product(_.range(strings), _.range(frets)))
    .filter(isNote(note, tuning))
    .value();

The isNote helper function returns whether the note at the given string/fret is the note we’re looking for, regardless of octave.

Filtering Out Doubled Strings

Currently, our chord voicing generator looks like this:

const isNote = (note, tuning) => ([string, fret]) =>
  (tuning[string] + fret) % 12 === note;

const findNoteOnFretboard = (frets, strings, tuning) => note =>
  _.chain(_.product(_.range(strings), _.range(frets)))
  .filter(isNote(note, tuning))
  .value();

const voicings = (
  notes,
  tuning = [40, 45, 50, 55, 59, 64],
  frets = 18,
  strings = _.size(tuning)
) =>
  _.chain(notes)
    .map(findNoteOnFretboard(frets, strings, tuning))
    .thru(notesOnFretboard => _.product(...notesOnFretboard))
    .value();

Not bad. We’ve managed to generate all possible voicings for a given chord in less than twenty lines of code! Unfortunately, we have a problem. Our solution generates impossible voicings!

The first problem is that it can generate voicings with two notes on the same string:

On a stringed instrument like the guitar, it’s impossible to sound both the C and E notes simultaneously. We’ll need to reject these voicings by looking for voicings with “doubled strings”. That is, voicings with two or more notes played on the same string:

const voicings = (
  notes,
  tuning = [40, 45, 50, 55, 59, 64],
  frets = 18,
  strings = _.size(tuning)
) =>
  _.chain(notes)
    .map(findNoteOnFretboard(frets, strings, tuning))
    .thru(notesOnFretboard => _.product(...notesOnFretboard))
    .reject(hasDoubledStrings)
    .value();

Our hasDoubledStrings helper simply checks if the size of the original voicing doesn’t match the size of our voicing after removing duplicated strings:

const hasDoubledStrings = chord =>
  _.size(chord) !==
  _.chain(chord)
    .map(_.first)
    .uniq()
    .size()
    .value();

Filtering Out Impossible Stretches

Unfortunately, our solution has one last problem. It can generate chords that are simply too spread out for any human to play. Imagine trying to stretch your hand enough to play this monster of a voicing:

No good. We’ll need to reject these voicings that have an unplayable stretch:

const voicings = (
  notes,
  tuning = [40, 45, 50, 55, 59, 64],
  frets = 18,
  maxStretch = 5,
  strings = _.size(tuning)
) =>
  _.chain(notes)
    .map(findNoteOnFretboard(frets, strings, tuning))
    .thru(notesOnFretboard => _.product(...notesOnFretboard))
    .reject(hasDoubledStrings)
    .reject(hasUnplayableStretch(maxStretch))
    .value();

Let’s keep things simple for now and assume that an “unplayable stretch” is anything over five frets in distance from one note in the voicing to another.

const hasUnplayableStretch = maxStretch => chord => {
  let [, min] = _.minBy(chord, ([string, fret]) => fret);
  let [, max] = _.maxBy(chord, ([string, fret]) => fret);
  return max - min > maxStretch;
};

Expansion and Contraction

Our voicings function now generates all possible voicings for any given set of notes. A nice way of visualizing all of these voicings on the fretboard is with a heat map. Here are all of the C major voicings we’ve generated with our new Cartesian product powered voicings function:

The darker the fret, the more frequently that fret is used in the set of possible voicings. Click any fret to narrow down the set of voicings.

The Cartesian product, at least in the context of algorithms, embodies the idea of expansion and contraction. I’ve found that over-generating possible results, and culling out impossibilities leads to incredibly clear and concise solutions.

Be sure to add the Cartesian product to your programming tool box!