Two mechanisms for generating infinite families of pairing bijections
Paul Tarau · 2013
We explore two general mechanisms for producing pairing bijections (bijective functions defined from N2 → N). The first mechanism, using n-adic valuations results in parameterized algorithms generating a countable family of distinct pairing bijections. The second mechanism, using characteristic functions of subsets of N provides 2N distinct pairing bijections. Mechanisms to combine such pairing bijections and their application to generate families of permutations of N are also described. The paper uses a small subset of the functional language Haskell to provide executable specifications of various the functions defined in a literate programming style.