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:
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:
