Posts Tagged ‘Cartesian Product’

The Cartesian Product

This is the first technical post on this blog after seven years of writing.

Recently as I was thinking about how to automate flight search with my flight deals website, Concorde, I realized that I wanted to be able to input any two sets of airport pairs, and then find the cheapest flights between those two airports. For example, I wanted to be able to discover the cheapest flights between the New York-area airports and a dozen or so airports in the Caribbean. The two sets of airports look something like this:

originAirports = [(“EWR”),(“JFK”),(“LGA”)]

destinationAirports = [(“NAS”),(“SJU”),(“SXM”),(“STT”),(“GCM”), (“SDQ”),(“MBJ”),(“AUA”),(“CUR”),(“CUN”),(“PTP”),(“PLS”)]

In order to search flights between all of the possible pairs of airports given the two distinct sets, I need to generate a third set, a list of all possible airport pairs between the two sets. The strategy for accomplishing this task, the Cartesian product, is a topic that I had covered in my discrete mathematics class at Wake Forest. According to Wikipedia, this is how the Cartesian product works:

That is, for sets A and B, the Cartesian product A × B is the set of all ordered pairs(a, b) where a is an element of A and b is an element of B.

Wikipedia’s definition is a fancy way of saying that in order to generate a set of all possible airport pairs given two other sets of airports, I need to multiply the original sets together. Fortunately, Ruby (1.9+) has this functionality built-in with the “product” method:

airportPairs = originAirports.product(destinationAirports)

=> [[“EWR”, “NAS”], [“EWR”, “SJU”], [“EWR”, “SXM”], [“EWR”, “STT”], [“EWR”, “GCM”], [“EWR”, “SDQ”], [“EWR”, “MBJ”], [“EWR”, “AUA”], [“EWR”, “CUR”], [“EWR”, “CUN”], [“EWR”, “PTP”], [“EWR”, “PLS”], [“JFK”, “NAS”], [“JFK”, “SJU”], [“JFK”, “SXM”], [“JFK”, “STT”], [“JFK”, “GCM”], [“JFK”, “SDQ”], [“JFK”, “MBJ”], [“JFK”, “AUA”], [“JFK”, “CUR”], [“JFK”, “CUN”], [“JFK”, “PTP”], [“JFK”, “PLS”], [“LGA”, “NAS”], [“LGA”, “SJU”], [“LGA”, “SXM”], [“LGA”, “STT”], [“LGA”, “GCM”], [“LGA”, “SDQ”], [“LGA”, “MBJ”], [“LGA”, “AUA”], [“LGA”, “CUR”], [“LGA”, “CUN”], [“LGA”, “PTP”], [“LGA”, “PLS”]]

Or view the results as they would appear in the Terminal:

Screen Shot 2016-02-28 at 4.19.46 PM

And that’s it! Just three commands in Terminal to generate a list of all possible airport combinations, the Cartesian Product, between a set of New York-area airports and popular Caribbean destinations.

I hope this was helpful!

Related resources:

 

28

02 2016