Deriving a Fast Inverse of the Generalized Cantor N-tupling Bijection

Paul Tarau
We attack an interesting open problem (an efficient algorithm to invert the generalized Cantor N-tupling bijection) and solve it through a sequence of equivalence preserving transformations of logic programs, that take advantage of unique strengths of this programming paradigm. An extension to set and multiset tuple encodings, as well as a simple application to a "fair-search" mechanism illustrate practical uses of our algorithms. The code in the paper (a literate Prolog program, tested with SWI-Prolog...