Skip to content

Instantly share code, notes, and snippets.

@keineahnung2345
Created October 1, 2021 14:30
Show Gist options
  • Save keineahnung2345/8b2ea500e7f56a4a1a8fee7dcc03ce52 to your computer and use it in GitHub Desktop.
Save keineahnung2345/8b2ea500e7f56a4a1a8fee7dcc03ce52 to your computer and use it in GitHub Desktop.
Cantor pairing function for three integers(negative allowed)
# https://www.vertexfragment.com/ramblings/cantor-szudzik-pairing-functions/
# https://stackoverflow.com/questions/38965931/hash-function-for-3-integers
# https://math.stackexchange.com/questions/222709/inverting-the-cantor-pairing-function
def normalize(x):
# this function make cantor pairing function work for negative numbers
return 2*x if (x>=0) else (-2*x-1)
def normalize_inv(x):
return x//2 if (x % 2 == 0) else -(x+1)//2
def cantor(a, b):
return (a+b)*(a+b+1)//2 + b
def cantor_inv(z):
n = (-1+pow(1+8*z, 0.5))//2
b = z - n*(n+1)//2
a = n - b
return a, b
if __name__ == "__main__":
n = 3
for a in range(-n, n+1):
for b in range(-n, n+1):
for c in range(-n, n+1):
na = normalize(a)
nb = normalize(b)
nc = normalize(c)
z = cantor(cantor(na, nb), nc)
inab, inc = cantor_inv(z)
ic = normalize_inv(inc)
ina, inb = cantor_inv(inab)
ia = normalize_inv(ina)
ib = normalize_inv(inb)
print(a, b, c, " -> ", z, " -> ", ia, ib, ic)
print("===============")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment