Enumerating all 3-tuples

[Robin Becker]

On 21/03/2018 05:14, Steven D'Aprano wrote:
> On Tue, 13 Mar 2018 23:56:37 +0100, Denis Kasak wrote:
> 
> [...]
>> The triples can be viewed as a pair of a pair and a natural number:
>>
>> (1,1),1 (1,1),2 (1,1),3 ...
>> (2,1),1 (2,1),2 (2,1),3 ...
>> (1,2),1 (1,2),2 (1,2),3 ...
> 
> [...]
>> This leads fairly naturally to the implementation.
>>
>>       from itertools import accumulate, count
>>
>>       def c(i):
>>           """
...........
> That looks interesting, I haven't had a chance to play with it in a lot
> of detail yet, but it looks to me like every time you generate a triple,
> it starts counting up from 1.
> 
> So iterating over c3(1), c3(2), c3(4), ... c3(something big) is going to
> have O(N**2) performance. It's like the old joke about the Polish painter:
>
This cantor inverse is much faster; it uses the integer sqrt from here

http://code.activestate.com/recipes/577821-integer-square-root-function/

so far as I can tell it works for the cantor below

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

def isqrt(x):
	if x < 0:
		raise ValueError('square root not defined for negative numbers')
	n = int(x)
	if n == 0:
		return 0
	a, b = divmod(n.bit_length(), 2)
	x = 2**(a+b)
	while True:
		y = (x + n//x)//2
		if y >= x:
			return x
		x = y

def inverse_cantor(z):
	w = int((isqrt(8*z+1)-1)//2)
	t = (w*(w+1))>>1
	j = z - t
	i = w - j
	return i, j

but it doesn't agree with Denis' inverse I guess because this is defined on non-negative integers, but his functions are defined 
on positive integers.

> http://global.joelonsoftware.com/English/Articles/BacktoBasics.html
> 
> Since that's exactly what I need to do, that might be a problem.
> 
> On the other hand, I doubt I'll need to generate more than a few thousand
> of these, so it might be fast enough. I guess I have to run some
> benchmarks to find out.
> 
> But however they turn out, I appreciate your time and code. Thanks heaps!
> 
> 
> 


-- 
Robin Becker