# Is there a bijective function which maps an integer vector onto a single number?

I am looking for a function that maps an integer vector onto a single number. Actually it is a algorithmic problem I am having. But there must be such functions around, especially when thinking of cryptography.

-
Do you want to map an integer vector to a rational (even Real) number or an integer number? –  Bardia Jan 26 '12 at 12:47
I want to map an integer vector to an intger number. –  steffi Jan 26 '12 at 15:43

Assuming the length is fixed, you can just interleave the bits of the numbers.

For example, if the vector is $(1,2,3)$ we have $1 = 01_2$, $2=10_2$, $3=11_2$, so the result is $53 = 110101_2$. The first bit of $53$ is the first bit of $1$, the second bit is the first bit of $2$, ..., the sixth bit of $53$ is the second bit of $3$. This works essentially the same way if the values are real. A similar construction is used to prove the cardinal equation 𝕮$^2$ = 𝕮.

To encode a 3-vector this way in C:

#include <stdio.h>
#include <stdint.h>

uint32_t zip(uint8_t a, uint8_t b, uint8_t c) {
int i;
uint32_t d = 0;
for (i = 0; i < 8; ++i) {
d |= (a & (1 << i)) << (0 + (i << 1));
d |= (b & (1 << i)) << (1 + (i << 1));
d |= (c & (1 << i)) << (2 + (i << 1));
}
return d;
}

int main(int argc, char **argv) {
printf("%u\n", zip(1, 2, 3));
return 0;
}

-
Thanks! The point is that I am actually working on a compression problem. So, by using this transformation, unfortunately I do not save any bits... –  steffi Jan 26 '12 at 9:44
You can't save any bits if you want a bijection unless you have assumptions about the complexity of the input vector. If you just want to uniquely identify vectors for practical purposes, use a hash function. –  Dan Brumleve Jan 26 '12 at 9:57

Here's something that almost works: map the integer vector $(a_1,a_2,\dots,a_n)$ to the (rational) number $2^{a_1}3^{a_2}\times\cdots\times p_n^{a_n}$, where the numbers $2,3,\dots,p_n$ are the first $n$ primes. The Unique Factorization Theorem almost guarantees that no two distinct vectors go to the same number.

The problem is with zeros: $(-5,6,0)$ and $(-5,6)$ both go to $729/32$. We can fix it by letting $f$ be any 1-1 map from the integers to the nonzero integers, for example, $f(x)=x+1$ if $x\ge0$, $f(x)=x$ if $x\lt0$, and then map $(a_1,a_2,\dots,a_n)$ to $2^{f(a_1)}3^{f(a_2)}\times\cdots\times p_n^{f(a_n)}$. This map answers the question.

EDIT: After I posted what's above, OP commented elsewhere that the image is to be an integer. This can be achieved by letting $f$ be any 1-1 map from the integers to the positive integers, for example, $f(n)=2n$ if $n\gt0$, $f(n)=1-2n$ if $n\le0$. Now $(-5,6,0)$ maps to $2^{11}3^{12}5$, and $(-5,6)$ maps to $2^{11}3^{12}$. The map is not quite a bijection, e.g., nothing maps to $3$.

-

You could use an adaptation of Cantor's method of counting the rational numbers. Take a two-dimensional vector instead of the rational numbers, include the numbers with alternationg sign to get the negatives and you are there. For higher dimension, you could use the same method rescursively.

-