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
--
https://mail.python.org/mailman/listinfo/python-list
