2

I am looking for a simple expression to convert ordered pairs from $[0,n]$ to the first smallest subset of $\mathbb N$. For example if $n = 3$:

$$ (0, 1) \rightarrow 0$$ $$ (0, 2) \rightarrow 1$$ $$ (0, 3) \rightarrow 2$$ $$ (1, 2) \rightarrow 3$$ $$ (1, 3) \rightarrow 4$$ $$ (2, 3) \rightarrow 5$$

What could be an explicit formula for that?

To rephrase, I am looking for a formula $f_n(i, j)$ where $0 \le i < j \le n$ such that $0 \le f_n(i, j) < \left ( ^{n}_{2}\right )$ and $f_n$ is bijective. I would also like if possible the inverse bijection to retrieve $i$ and $j$ from an image of $f_n$.

The values of the function do not matter as long as the set of values is the same.

Cantor pairing functions are not applicable here because the bijection is not infinite.

Mikaël Mayer
  • 247
  • 1
  • 9
  • This might be what you're looking for? – Peter Košinár Dec 30 '13 at 13:49
  • I added the link in the question to state that it does not help. But thank you for trying. – Mikaël Mayer Dec 30 '13 at 13:51
  • The infiniteness of the bijection is usually not a problem; if you restrict the inputs to integers not exceeding $n$, it'll work quite nicely. But you're right in thinking I overlooked the "ordered" part of your requirements; it'd require one extra tweak before being usable directly. – Peter Košinár Dec 30 '13 at 14:02
  • What's wrong with the Cantor pairing function? The bijection is infinite. – Mitch Dec 30 '13 at 14:47

2 Answers2

3

If you are lazy, a simple adaptation of the Cantor Pairing Function $\pi$ works quite well:

$$f(x,y):=\pi(x,y-x-1) = \frac{1}{2}y(y+1) - x - 1$$

As a bonus, it doesn't depend on $n$, so the same mapping can be extended to any $n$, without changing the resulting values.

Going backwards is quite easy too. Since $\frac{1}{2}y(y+1)-x-1 = \frac{1}{2}(y+\frac{1}{2})^2 - x - \frac{9}{8}$, if we want to "unpack" number $N$, we can simply calculate $$y = \left\lceil \sqrt{2N + 9/4}-\frac{1}{2}\right\rceil$$ and then $$x = \frac{1}{2}y(y+1)-1 - N$$

Peter Košinár
  • 10,810
  • That would be awesome if the reverse bijection was so easy to compute. – Mikaël Mayer Dec 30 '13 at 14:16
  • 1
    ... and the reverse actually is quite easy to compute too; even though it might look scary at the first glance (see the updated answer for details). – Peter Košinár Dec 30 '13 at 14:39
  • This freaks me out but ok. I will have a look at how to implement a square root taking not too much calculus. – Mikaël Mayer Dec 30 '13 at 15:45
  • @MikaëlMayer What is the setting you're working in? I mean -- are you trying to implement it on computer; or on some device with restricted computing power; or perhaps doing it "by hand"? Since you're not actually interested in the square root, but (roughly speaking) only its integer part, you can avoid doing any non-integer arithmetics at all. – Peter Košinár Dec 30 '13 at 16:11
  • Indeed, thank you for asking, I am trying to do some low-level optimization of direct acyclic graph representations, and this was a problem I was stumbling on. How would you avoid computing the square root? – Mikaël Mayer Dec 30 '13 at 16:13
  • 1
    One (certainly not the most efficient) option is to preform simple binary search over the range $[0,n]$ for the value of $y$; if $\frac{1}{2}y(y+1)-1$ is smaller than $N$, the actual value lies in upper half; otherwise it lies in the bottom half of the interval. But do you really really need to pack everything into the shortest range possible? Combining the two numbers as $(n+1)x+y$ makes it trivial to extract both $x$ and $y$, while using just twice the minimum range. – Peter Košinár Dec 30 '13 at 16:18
  • Good spot. I did not think about that. Just one division to recover y. – Mikaël Mayer Dec 30 '13 at 16:47
1

You can create a bijection from your set of pairs $\{(i,j)\in \mathbb N^2|\,0\leq i<j\leq n\}$ to $\{(i,)\in\mathbb N^2|\,0\leq i\leq n-1,\, 0\leq j\leq n-1-i\}$, which are the first $n$ diagonals of the cantor pairing function, with $f:(i,j)\mapsto(i,j-i-1)$. ($f^{-1}:(i,j)\mapsto(i,i+j+1)$) Then, you can apply the cantor pairing function to $f(i,j)$ to obtain $k$ and retrieve the original $(i,j)$ with $f^{-1}(\pi^{-1}(k))$

Ragnar
  • 6,233