Home > Uncategorized > 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:

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

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
> 

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

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
About these ads
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: