Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Cantor pairing function
// http://en.wikipedia.org/wiki/Pairing_function
package main
import (
"fmt"
"math"
)
func InvertedCantorPairing(z int) (int, int) {
w := int(math.Floor((math.Sqrt(float64(8*z+1)) - 1) / 2))
t := (w*w + w) / 2
y := z - t
x := w - y
return x, y
}
func CantorPairing(k1, k2 int) int {
return (k1+k2)*(k1+k2+1)/2 + k2
}
func main() {
for i := 0; i < 100; i++ {
x, y := InvertedCantorPairing(i)
fmt.Println(i, x, y, CantorPairing(x, y))
}
}
@alvarolm

This comment has been minimized.

Copy link

@alvarolm alvarolm commented Sep 1, 2015

thanks

@dyarosla

This comment has been minimized.

Copy link

@dyarosla dyarosla commented Jan 20, 2018

Correct me if I'm wrong, but to avoid overflow with big (k1, k2) we should use
(k1/2+k2/2)*(k1+k2+1) + k2

This is similar in nature to what you'd do for

(a+b)/2

You'd instead code it as
a/2 + b/2

Because for large (a, b), where a+b > MAX_INT, we would still get a usable result.

@shaunc

This comment has been minimized.

Copy link

@shaunc shaunc commented Jan 19, 2019

@dyarosla -- rounding down for int division, we have:

(3+3)/2 = 6/2 = 3
3/2 + 3/2 = 1 + 1 = 2 

Your method works for approximate results, but not for exact ones.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment