# Construct an unique index from two integer (Pairing Function)

## Construct an unique index from two integer (Pairing Function)

Recently, I need to construct an unique index from two integer. The best solution I found is the Pairing function.

Pairing function is an one to one and onto function that map two integers to a single integer. The definition as follows:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 `pair<-``function``(x,y){` `  ``0.5*(x+y)*(x+y+1) +  x` `}` `unpair<-``function``(z){` `  ``w= ``floor``( (``sqrt``(8*z+1) - 1)/2 )` `  ``t = w*(w+1)/2` `  ``cbind``(z-t,w-z+t)` `}` `foreach ``(i = 0:4,.combine=rbind) %do% {` `  ``x<-0:i` `  ``y<-i:0` `  ``key<-``pair``(x,y)` `  ``unpair_key <- ``unpair``(key)` `  ``cbind``(x,y,key=key,unpair_key=unpair_key)` `}` `      ``x y key x y` ` ``[1,] 0 0   0 0 0` ` ``[2,] 0 1   1 0 1` ` ``[3,] 1 0   2 1 0` ` ``[4,] 0 2   3 0 2` ` ``[5,] 1 1   4 1 1` ` ``[6,] 2 0   5 2 0` ` ``[7,] 0 3   6 0 3` ` ``[8,] 1 2   7 1 2` ` ``[9,] 2 1   8 2 1` `[10,] 3 0   9 3 0` `[11,] 0 4  10 0 4` `[12,] 1 3  11 1 3` `[13,] 2 2  12 2 2` `[14,] 3 1  13 3 1` `[15,] 4 0  14 4 0`

If ordering of `x` and `y` is not important, we can swap `x` and `y` if `x>y`. However, the Pairing function is not one to one and we can not back out `x` and `y` with `z`

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 `pair<-``cmpfun``(``function``(x,y,ordering_matter=``TRUE``){` `  ``if ``(ordering_matter){` `    ``return``(0.5*(x+y)*(x+y+1) + x)` `  ``} ``else``{` `    ``swap <- x>y` `    ``return``(0.5*(x+y)*(x+y+1) +  (x* !swap) + (y*swap ))` `  ``}` `})` `foreach ``(i = 0:4,.combine=rbind) %do% {` `  ``x<-0:i` `  ``y<-i:0` `  ``key<-``pair``(x,y,ordering_matter=``FALSE``)` `  ``unpair_key <- ``unpair``(key)` `  ``cbind``(x,y,key=key,unpair_key=unpair_key)` `}` `      ``x y key x y` ` ``[1,] 0 0   0 0 0` ` ``[2,] 0 1   1 0 1` ` ``[3,] 1 0   1 0 1` ` ``[4,] 0 2   3 0 2` ` ``[5,] 1 1   4 1 1` ` ``[6,] 2 0   3 0 2` ` ``[7,] 0 3   6 0 3` ` ``[8,] 1 2   7 1 2` ` ``[9,] 2 1   7 1 2` `[10,] 3 0   6 0 3` `[11,] 0 4  10 0 4` `[12,] 1 3  11 1 3` `[13,] 2 2  12 2 2` `[14,] 3 1  11 1 3` `[15,] 4 0  10 0 4` `> `

### Two Integers

If we have more than two integers, we can apply the Pairing function in a nested manner.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 `nestedPair<-``function``(x){` `  ``ncol_x = ``ncol``(x)` `  ``if``(ncol_x==1){` `    ``return``(x)` `  ``} ``else` `if``(ncol_x ==2) {` `    ``return``(``pair``(x[,1],x[,2]))` `  ``} ``else` `if ``( ncol_x > 2){` `    ``return``(``pair``( x[,1] ,``nestedPair``(x[,2:ncol_x]) ) )` `  ``}` `}` `nestedUnpair<-``function``(x,order){` `  ``if``(order==1){` `    ``return``(``unpair``(x))` `  ``} ``else` `if``(order >1) {` `    ``out <- ``unpair``(x)` `    ``return``(``cbind``(out[,1],``nestedUnpair``(out[,2],order-1)))` `  ``}` `}` `x<-``expand.grid``(0:2,0:2,0:2)` `key <- ``nestedPair``(x)` `unpair_key <- ``nestedUnpair``(key,2)` `cbind``(x=x,key=key,unpair_key=unpair_key)` `   ``x.Var1 x.Var2 x.Var3 key unpair_key.1 unpair_key.2 unpair_key.3` `1       0      0      0   0            0            0            0` `2       1      0      0   2            1            0            0` `3       2      0      0   5            2            0            0` `4       0      1      0   3            0            1            0` `5       1      1      0   7            1            1            0` `6       2      1      0  12            2            1            0` `7       0      2      0  15            0            2            0` `8       1      2      0  22            1            2            0` `9       2      2      0  30            2            2            0` `10      0      0      1   1            0            0            1` `11      1      0      1   4            1            0            1` `12      2      0      1   8            2            0            1` `13      0      1      1  10            0            1            1` `14      1      1      1  16            1            1            1` `15      2      1      1  23            2            1            1` `16      0      2      1  36            0            2            1` `17      1      2      1  46            1            2            1` `18      2      2      1  57            2            2            1` `19      0      0      2   6            0            0            2` `20      1      0      2  11            1            0            2` `21      2      0      2  17            2            0            2` `22      0      1      2  28            0            1            2` `23      1      1      2  37            1            1            2` `24      2      1      2  47            2            1            2` `25      0      2      2  78            0            2            2` `26      1      2      2  92            1            2            2` `27      2      2      2 107            2            2            2`

Recientemente, necesito construir un índice único a partir de dos enteros. La mejor solución que encontré es la función de emparejamiento.

La función de emparejamiento es uno a uno y en función que asigna dos enteros a un solo entero. La definición de la siguiente manera:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 `pair<-``function``(x,y){` `  ``0.5*(x+y)*(x+y+1) +  x` `}` `unpair<-``function``(z){` `  ``w= ``floor``( (``sqrt``(8*z+1) - 1)/2 )` `  ``t = w*(w+1)/2` `  ``cbind``(z-t,w-z+t)` `}` `foreach ``(i = 0:4,.combine=rbind) %do% {` `  ``x<-0:i` `  ``y<-i:0` `  ``key<-``pair``(x,y)` `  ``unpair_key <- ``unpair``(key)` `  ``cbind``(x,y,key=key,unpair_key=unpair_key)` `}` `      ``x y key x y` ` ``[1,] 0 0   0 0 0` ` ``[2,] 0 1   1 0 1` ` ``[3,] 1 0   2 1 0` ` ``[4,] 0 2   3 0 2` ` ``[5,] 1 1   4 1 1` ` ``[6,] 2 0   5 2 0` ` ``[7,] 0 3   6 0 3` ` ``[8,] 1 2   7 1 2` ` ``[9,] 2 1   8 2 1` `[10,] 3 0   9 3 0` `[11,] 0 4  10 0 4` `[12,] 1 3  11 1 3` `[13,] 2 2  12 2 2` `[14,] 3 1  13 3 1` `[15,] 4 0  14 4 0`

Si el orden de `x` e `y` no es importante, podemos intercambiar `x`e y si `x>y`. Sin embargo, la función de emparejamiento no es uno a uno y no podemos retroceder x e y con z

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 `pair<-``cmpfun``(``function``(x,y,ordering_matter=``TRUE``){` `  ``if ``(ordering_matter){` `    ``return``(0.5*(x+y)*(x+y+1) + x)` `  ``} ``else``{` `    ``swap <- x>y` `    ``return``(0.5*(x+y)*(x+y+1) +  (x* !swap) + (y*swap ))` `  ``}` `})` `foreach ``(i = 0:4,.combine=rbind) %do% {` `  ``x<-0:i` `  ``y<-i:0` `  ``key<-``pair``(x,y,ordering_matter=``FALSE``)` `  ``unpair_key <- ``unpair``(key)` `  ``cbind``(x,y,key=key,unpair_key=unpair_key)` `}` `      ``x y key x y` ` ``[1,] 0 0   0 0 0` ` ``[2,] 0 1   1 0 1` ` ``[3,] 1 0   1 0 1` ` ``[4,] 0 2   3 0 2` ` ``[5,] 1 1   4 1 1` ` ``[6,] 2 0   3 0 2` ` ``[7,] 0 3   6 0 3` ` ``[8,] 1 2   7 1 2` ` ``[9,] 2 1   7 1 2` `[10,] 3 0   6 0 3` `[11,] 0 4  10 0 4` `[12,] 1 3  11 1 3` `[13,] 2 2  12 2 2` `[14,] 3 1  11 1 3` `[15,] 4 0  10 0 4` `> `

Si tenemos más de dos enteros, podemos aplicar la función de emparejamiento de forma anidada.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 `nestedPair<-``function``(x){` `  ``ncol_x = ``ncol``(x)` `  ``if``(ncol_x==1){` `    ``return``(x)` `  ``} ``else` `if``(ncol_x ==2) {` `    ``return``(``pair``(x[,1],x[,2]))` `  ``} ``else` `if ``( ncol_x > 2){` `    ``return``(``pair``( x[,1] ,``nestedPair``(x[,2:ncol_x]) ) )` `  ``}` `}` `nestedUnpair<-``function``(x,order){` `  ``if``(order==1){` `    ``return``(``unpair``(x))` `  ``} ``else` `if``(order >1) {` `    ``out <- ``unpair``(x)` `    ``return``(``cbind``(out[,1],``nestedUnpair``(out[,2],order-1)))` `  ``}` `}` `x<-``expand.grid``(0:2,0:2,0:2)` `key <- ``nestedPair``(x)` `unpair_key <- ``nestedUnpair``(key,2)` `cbind``(x=x,key=key,unpair_key=unpair_key)` `   ``x.Var1 x.Var2 x.Var3 key unpair_key.1 unpair_key.2 unpair_key.3` `1       0      0      0   0            0            0            0` `2       1      0      0   2            1            0            0` `3       2      0      0   5            2            0            0` `4       0      1      0   3            0            1            0` `5       1      1      0   7            1            1            0` `6       2      1      0  12            2            1            0` `7       0      2      0  15            0            2            0` `8       1      2      0  22            1            2            0` `9       2      2      0  30            2            2            0` `10      0      0      1   1            0            0            1` `11      1      0      1   4            1            0            1` `12      2      0      1   8            2            0            1` `13      0      1      1  10            0            1            1` `14      1      1      1  16            1            1            1` `15      2      1      1  23            2            1            1` `16      0      2      1  36            0            2            1` `17      1      2      1  46            1            2            1` `18      2      2      1  57            2            2            1` `19      0      0      2   6            0            0            2` `20      1      0      2  11            1            0            2` `21      2      0      2  17            2            0            2` `22      0      1      2  28            0            1            2` `23      1      1      2  37            1            1            2` `24      2      1      2  47            2            1            2` `25      0      2      2  78            0            2            2` `26      1      2      2  92            1            2            2` `27      2      2      2 107            2            2            2`