3
$\begingroup$

I want to encode $n$ natural numbers into one natural number. Also, I should be able to decode it back. I tried Gödel's encoding scheme, but it takes a lot of space (doesn't fit into a double) and requires a lot of computation. Is there a better scheme?

Thanks in advance.

$\endgroup$
4
  • 1
    $\begingroup$ By what standard are you going to measure 'better'? A random guess on my uneducated behalf hints to me that given any bounded set of $n$ numbers (say by $2^K$, $n$ arbitrary), the complexity of encoding these as a single number will probably escape the bound. What if you are trying to encode $2^K -n-1, 2^k - n ,\ldots, 2^K - 1$? $\endgroup$
    – David Roberts
    Jul 1, 2011 at 10:46
  • 9
    $\begingroup$ A trivial counting argument tells you that it is impossible to encode $n$ $m$-bit integers into less than $nm$ bits. Anyway, this does not look like research-level math question, see the faq. $\endgroup$ Jul 1, 2011 at 10:48
  • $\begingroup$ I do not understand why this question was downvoted. I find an interesting question whose answer can be useful for programming. $\endgroup$ Jul 1, 2011 at 16:23
  • 7
    $\begingroup$ Without more restrictions, this doesn't seem to be a research level mathematics problem. In addition, this question could be rewritten to be much clearer and to be informative. I can immediately think of several encoding schemes, but I don't know what Gödel's encoding scheme was for $\mathbb{N}^n$, or exactly why that was unsatisfactory. If you want such an encoding scheme for programming, you may want additional properties such as that the usual operations (e.g., addition, comparison) on the results have some meaning on the decoded number, at least for some restricted set of inputs. $\endgroup$ Jul 1, 2011 at 17:16

8 Answers 8

12
$\begingroup$

One can give an explicit bijection $f_n:\mathbb{N}^n\to\mathbb{N}$. In the case $n=4$ it is $$ f_4(p,q,r,s) = \left(\begin{matrix} p+q+r+s+3 \\\\ 4\end{matrix}\right)+ \left(\begin{matrix} p+q+r+2 \\\\ 3\end{matrix}\right)+ \left(\begin{matrix} p+q+1 \\\\ 2\end{matrix}\right)+p $$ The general case follows the obvious pattern. We can order $\mathbb{N}^n$ as follows: if $a_1+\dotsb+a_n\lt b_1+\dotsb+b_n$ we declare that $a\lt b$, but if we have a tie according to this test then we instead compare $a_1+\dotsb+a_{n-1}$ with $b_1+\dotsb+b_{n-1}$, and so on. Then $f_n(a)=|\{b\in\mathbb{N}^n:b \lt a\}|$. To find $f_4^{-1}(k)$ you first find the largest $u$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)\leq k$, then the largest $v$ such that $\left(\begin{matrix}u+3\\\\ 4\end{matrix}\right)+ \left(\begin{matrix}v+2\\\\ 3\end{matrix}\right)\leq k$, and so on. This is not quite as good as a formula but at least it is a fairly straightforward algorithm. One can check that $f_4(p,q,r,s)<2^{64}$ provided that $p+q+r+s\lt 145053$, so 64 bit integers are enough for a reasonable range of values.

$\endgroup$
3
  • 2
    $\begingroup$ That's cute! But in practice, if you have a permanent restriction to 64 bits, and $n=4$, you probably may as well use my scheme (below) with $B = 2^{16}$. It's worth mentioning that, with that value of $B$, you can rapidly encode and decode using binary shift operations. $\endgroup$ Jul 1, 2011 at 12:38
  • 3
    $\begingroup$ We might as well add where this is coming from geometrically. For $n = 2$, it's the inverse of the usual enumeration of $\mathbb{N}^2$ where one skims along diagonals parallel to $x+y = 0$ in succession, and the starting point on each diagonal is on the $x$-axis. Similarly, for $n=3$, it's inverse to an enumeration which proceeds by filling out each successive triangle parallel to $x+y+z = 0$. $\endgroup$
    – Todd Trimble
    Jul 1, 2011 at 16:27
  • $\begingroup$ (Well, I guess Neil pretty much said that in different words.) $\endgroup$
    – Todd Trimble
    Jul 1, 2011 at 16:29
9
$\begingroup$

I'd just like to point out that more than one of the answers above can be viewed as follows. The problem becomes easy if, instead of working with natural numbers, you work with finite strings over some fixed alphabet. To code a finite sequence of strings, just concatenate them, inserting some punctuation to show where one string ends and the next begins (or assuming some a priori information on the input that can determine the break points without punctuation). To solve the problem for natural numbers rather than strings, identify numbers with strings in one of the well-known ways, for example the standard expansion in some base $b$. The counting argument mentioned in some previous answers shows that you can't do significantly better than this. (In some cases you can do a little better by being clever about the punctuation.) In particular, Snark's interpretation of the question, asking for even a single integer to be compressed by coding, is implausible.

$\endgroup$
4
$\begingroup$

There is a series of good answers on StackOverflow and Quora, where I learned these go by the name pairing functions (related to dovetailing in computer science), can be generalized to any infinite sets, and iterated to encode arbitrary-length tuples as @Hugo illustrates.

In particular Szudzik's function is relatively efficient in computation and representation:

$$ ElegantPair (x, y) = \begin{cases} y^2 + x & x \neq max(x, y)\\ x^2 + x + y & x = max(x, y)\\ \end{cases} $$

and its inverse:

$$ ElegantUnpair (z) = \begin{cases} (z - \lfloor{\sqrt{z}}\rfloor^2, \lfloor{\sqrt{z}}\rfloor) & z - \lfloor{\sqrt{z}}\rfloor^2 < \lfloor{\sqrt{z}}\rfloor\\ (\lfloor{\sqrt{z}}\rfloor, z - \lfloor{\sqrt{z}}\rfloor^2 - \lfloor{\sqrt{z}}\rfloor) & z - \lfloor{\sqrt{z}}\rfloor^2 \geq \lfloor{\sqrt{z}}\rfloor\\ \end{cases} $$

Which looks like this:

enter image description here

$\endgroup$
4
$\begingroup$

Imagine the sequence of numbers that covers the two dimensional grid as follows:

Encoding two natural numbers into one

This gives you a very simple and compact way of encoding two numbers into one. Suppose that $a$ is the row, $b$ is the column and $N$ is the cell value at coordinates $(a,b)$.

You can easily verify that the encoding formula is just:

$$ N = \frac{(a+b)^2 + 3a + b}{2} $$

And the decoding, given $N$, is given by:

$$ s = \lfloor{\sqrt{2N}}\rfloor $$

$$ a = \frac{2N - s^2 - s}{2} $$ $$ b = s - a $$

Where $s$ is just an auxiliary variable, for conveniency, and $\lfloor \rfloor$ is the floor operator, that keeps only the integer part of a real number.

Now, you can extend this idea recursively. If you want to encode 3 numbers, encode the first with the second, and then encode the result with the third, to obtain a single integer. The same generalizes to k numbers. Just keep on going.

To decode you apply a similar reasoning. If you know that you expect k numbers, perform the decoding k-1 times, successively.

$\endgroup$
3
$\begingroup$

To a finite set $A\subset\mathbb{N}$ assign the natural number $\sum_{a\in A}2^a$. This map is bijective and requires little computation.

Of course this method is only good when the numbers to encode are different. If you want to encode a finite sequence of natural numbers into one, then I suggest the following. Write each number dyadically and and change the leading "1" into a "2". Then concatenate these strings and interpret the resulting sequence of digits 0,1,2 in base 3.

$\endgroup$
2
$\begingroup$

If you want to encode $n$ natural numbers $a_1,\ldots,a_n$, with $0\leq a_i < B$, then encode it as $a_1 + a_2B + \cdots + a_nB^{n-1}$.

$\endgroup$
1
  • $\begingroup$ This is the type of optimized encodings I had in mind with better informations about the type of (finite) sequences to encode. I remember an atari computer where the pointers were 32 bits... but only 24 of them were used to jump, so the eight others were used to pass a little more data to the functions :-) $\endgroup$ Jul 1, 2011 at 13:32
1
$\begingroup$

I'm not sure GH's answer is what was asked : as I understand it, the question is about an injection $\mathbb N^n\rightarrow\mathbb N$ for $n\geq2$.

The easy way is to note $p_1,\dots,p_n$ the first $n$ prime numbers and consider : $(d_1,\dots,d_n)\mapsto p_1^{d_1}\dots p_n^{d_n}$. Decoding is pretty easy in this case because you have to factor an integer knowing the prime numbers which appear.

EDIT: as I (and EJ 17 seconds before me) noted, this doesn't answer the question. So let me try another answer : generally no, it isn't possible to do better ; there's a definite limit of information you can encode in a given number of bits. But in more specific contexts, it is possible to do much better : for example for a pair of integers of the form $(m, m+1)$, you can get away with the same size to encode the pair as encoding $m$! So if you give us more specifics on the tuples you want to encode, then you'll get more interesting answers.

$\endgroup$
5
  • $\begingroup$ This is Gödel’s encoding, which the OP explicitly said they do not want. $\endgroup$ Jul 1, 2011 at 10:51
  • $\begingroup$ Sigh... reading the question again, I'm not answering correctly either... $\endgroup$ Jul 1, 2011 at 10:51
  • $\begingroup$ What's wrong with my answer? I gave a simple way of encoding an arbitrary sequence of natural numbers into a single natural number. The encoding takes little space and decoding is easy. $\endgroup$
    – GH from MO
    Jul 1, 2011 at 11:03
  • $\begingroup$ @GH Well, the question was about a semi-efficient encoding, and your method makes encoding a single integer take as many bits as the integer itself already. Of course, you'll notice that my first answer was even worse -- in fact I typed as an answer what I thought was the worse answer (both inefficient and excluded by the question)... thinking about something and typing another sometimes doesn't give good results... $\endgroup$ Jul 1, 2011 at 13:30
  • $\begingroup$ @Snark: Fair enough. My second method (added after your comment, I think) is more efficient. $\endgroup$
    – GH from MO
    Jul 1, 2011 at 15:08
1
$\begingroup$

What about Morton numbers ? They are obtained by interleaving the bits of one or more source numbers. If your source numbers are sufficiently small you can decode it back.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.