Enumerating all 3-tuples

[Robin Becker]

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