Calculate unique Integer representing a pair of integers

Question

I have a pair of positive integers $(x, y)$, with $(x, y)$ being different from $(y, x)$, and I'd like to calculate an integer "key" representing them in order that for a unique $(x, y)$ there is an unique key and no other pair $(w, z)$ could generate the same key.

I don't mind if we can/can't guess the pair values based on the key.

The key must be < 2,147,483,647 and the value of $x$ and $y$ as high as possible.

Any solution ?

Answer 1

You could use something like $\text{key}(x,y) = 2^{15}x + y$, where $x$ and $y$ are both restricted to the range $[0, 2^{15}]$. In programming terms, this just means stuffing $x$ into (roughly) half of your 31-bit space and $y$ into the other half.

It sounds like you are using a 32-bit integer variable in some programming language to represent the key. This is the reason for the limit of 2,147,483,647, I suppose. This means you really only have 31 bits available, because one bit is reserved for the sign of the integer. But this is slightly wasteful. If you use an unsigned integer variable (which is available in most programming languages), then you'll have 32 bits available. You can then use 16 bits for $x$, and 16 bits for $y$.

Using this sort of approach, recovering $x$ and $y$ from a given key is easy to code and extremely fast -- you just grab the relevant bits from the key variable. I can write the code, if you don't know how.

If you still want to use an int variable for the key (k), then the code (in C#) is:

int k = 32768*x + y;

With this approach, we require $x \le 65535$ (16 bits) and $y \le 32767$ (15 bits), and k will be at most 2,147,483,647, so it can be held in a 32-bit int variable.

If you are willing to use an unsigned int variable for the key (k), instead, as I suggested, then the code (again in C#) is:

uint k = 65536*x + y;

With this approach, we require $x \le 65535$ (16 bits) and $y \le 65535$ (16 bits), and k will be at most 4,294,967,295, which will fit in a 32-bit unsigned int variable.

Answer 2

I recommend the Cantor Pairing Function (wiki) defined by

$$\pi(x,y)=\frac12(x+y)(x+y+1)+y$$

The advantage is that when $x,y<K$ you have $\pi(x,y)<2(K+1)^2$, so you don't get extremly large keys with small values of $x$ and $y$.

The inverse function is described at the wiki page.

---

If you want to have all paris $x,y<2^{15}$, then you can go with the Szudzik's function:

$$\sigma(x,y)=\begin{cases}x^2+x+y & \text{if }x\geq y\\ x+y^2 & \text{otherwise}\end{cases}$$

Answer 3

Another unique key for non-negative integer pairs is

$$\mathrm{key}(x,y)=\max(x,y)^2+\max(y,2y-x)$$

This covers squares first, so should meet your conditions as well as not being limited to a given argument maximum. That is, if $\max(x,y)\lt2^n$, then $\mathrm{key}(x,y)\lt2^{2n}$.

$\hspace{4cm}$