# Re: Enumerating all 3-tuples

On 13/03/2018 11:14, Steven D'Aprano wrote:
On Mon, 12 Mar 2018 13:17:15 +0000, Robin Becker wrote:

It's possible to generalize the cantor pairing function to triples, but
that may not give you what you want. Effectively you can generate an
arbitrary number of triples using an iterative method. My sample code
looked like this

import math

def cantor_pair(k1,k2):
return (((k1+k2)*(k1+k2+1))>>1) + k2

def inverse_cantor_pair(z):
w = int((math.sqrt(8*z+1)-1)/2.0)
t = (w*(w+1))>>1
j = z - t
i = w - j
return i, j

I definitely want to avoid any round trips through float in order to use
sqrt.

But thanks for the code, I'll certainly steal it, er I mean study it for
future reference :-)

well I guess Cantor didn't worry about rounding errors :)

For high z there's an integer square root function which seems to work pretty
well here
http://code.activestate.com/recipes/577821-integer-square-root-function/

I'm not sure if there are any other sensible invertible pairing functions on non-negative integers; this page mentions a couple implemented in matlab

https://uk.mathworks.com/matlabcentral/fileexchange/44253-three-different-bijections-or-pairing-functions-between-n-and-n%5E2--including-cantor-polynomials-

and this describes the elegant pairing more

http://szudzik.com/ElegantPairing.pdf

It seems reasonable that a mapping N x N --> N should require a square root in
the inverse.
--
Robin Becker

--
https://mail.python.org/mailman/listinfo/python-list