Skip to content

Instantly share code, notes, and snippets.

@dyoo
Last active October 27, 2021 19:20
Show Gist options
  • Save dyoo/8062270 to your computer and use it in GitHub Desktop.
Save dyoo/8062270 to your computer and use it in GitHub Desktop.
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
Copy link

alvarolm commented Sep 1, 2015

thanks

@dyarosla
Copy link

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
Copy link

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