This is the code behind a blog post on pairing functions and a follow-up blog post on n-dimensional pairing functions. A pairing function returns the Cartesian product (all possible combinations) of two infinite streams. As explained in the post, the naive approaches to the Cartesian product do not work on infinite streams and existing pairing functions have some undesirable properties for programmatic purposes, for which I discuss solutions.
There are five methods described in the first post, each of which is coded up in a separate file:
box.py: Not an actual pairing function as it only works on finite lists not infinite streamscantor.py: The original pairing function by George Cantorszudzik.py: The elegant pairing function by Matthew Szudzikpeter.py: The superior pairing function by Rozsa Peteralternative.py: The alternative pairing function by me
There are two methods described in the second post, each of which is also coded up in a separate file:
multidimensional_box.py: Not an actual pairing function as it only works on a list of finite streamsmultidimensional_szudzik.py: An implementation of the n-dimensional generalization suggested in the elegant pairing function
Each method has three functions associated with it:
- Pairing function
(Index, Index) -> Indexwhich takes two indexes into streams and returns the index into the Cartesian product stream - Unpairing function
(Index) -> [Index, Index]which takes an index into the Cartesian product stream and produces two indexes into the individual streams - Cartesian product function
(Iterable[A], Iterable[B]) -> Iterable[[A, B]]which takes two streams and produces a stream of all possible combinations
Run any of the four pairing function scripts to cause a matplotlib figure illustrating that method to be displayed and the first 100 indexes of each method to be printed and validated. Run save_figures.py to recreate all the SVG versions of all the figures in the blog posts.
All code is made available under the MIT license. See license.txt.