In the previous post, I compared ways to take two infinite streams and generate a new stream that is all possible combinations of the elements in those streams. This post takes it up another level and generalizes this procedure to an arbitrarily long list of infinite streams. This is a trickier task than the 2-dimensional case, utilizing recursion into each dimension to cleanly generate all combinations.

Throughout this post, the caret ^ will indicate exponentiation and parentheses list(index) will be used to indicate indexing a list. As before, 0-indexing will be used because it makes the math simpler. 

Multidimensional box pairing function

Many programming languages have a function that will generate the Cartesian product of n lists of objects. In Python, it is called itertools.product.  The standard implementation starts with the first element from each list. Then it takes the second element from the last list and the first element from the remaining lists. It continues walking through the last list until it is exhausted. Then it increments the second to last list by one element and walks through the last list again.  This is repeated until the first list (which is walked slowest) is finally walked through once; at that point, all possible combinations have been generated. An algorithm to do this is straightforward to implement. It can with be done imperatively by updating a mutable list of indexes (like the Python version) or it can be done functionally using a recursive function (like the version below).

Multidimensional Szudzik pairing function

The two-dimensional Szudzik pairing function first divides the x-y plane into shells, each shell defined by max(x,y). This is a straightforward property to generalize. The n-dimensional space is divided into n-dimensional shells defined by max(x1, x2, ..., xn). Next, the two-dimensional Szudzik pairing function walks down each leg of the shell until the x==y element is reached. There are several ways to generalize this property.

A three-dimensional shell will have three faces. One sensible way to fill the shell would be to fill each face one at a time, treating each face as a plane to be filled with the two-dimensional Szudzik pairing function. Such a method could be recursively scaled up to arbitrary dimensions.

However, the original presentation briefly suggests in the penultimate slide a different generalization: pure lexicographical ordering within a shell. No implementation of the pairing function, unpairing function, or Cartesian product function is shown. But because this generalization is perfectly reasonable and the implementations straightforward to construct, it is the one I’ll show here.

The top level of the implementation is an infinite loop iterating over the shells, starting from the innermost shell. In each shell, all possible combinations of the streams are generated by taking each element in the first stream (until the shell is reached) and appending all possible combinations of the remaining streams, which is a recursive process. By itself, this recursive process would generate the Cartesian product of all elements within the cube bounded by the shell, like a multidimensional finite Cartesian product function. To restrict this process to just the elements on the shell, the process keeps track of whether or not an element on the shell has been emitted as it recurses. If it has not been emitted yet when the recursion reaches the final stream, only the final (shell) element of that stream is emitted, not the entire stream up to the shell, so that it guarantees that only points with at least one index on the shell are emitted within that shell’s iteration. 


I had spent considerable time making a multidimensional version of the Peter pairing function. I had succeeded in writing the product function, got most of the way done with the unpairing function, and was started on the pairing function. However, before I finished, I became convinced that the Szudzik pairing function was better suited for my real-life problem. A multidimensional pairing function that meets only requirement 1 from the previous post (i.e. do it by shells) is much easier to implement than one that also meets requirement 2 (i.e. alternate between legs).

The code used to generate the figures in this post is available on Github in the same repository as the previous post. Python versions of the pairing, unpairing, and Cartesian product functions are included.