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.
Is there a bijective function which maps an integer vector onto a single number?
-
0I want to map an integer vector to an intger number. – 2012-01-26
5 Answers
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#include 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; }
-
5You 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. – 2012-01-26
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 alternating sign to get the negatives and you are there. For higher dimension, you could use the same method rescursively.
If the vector contains fixed-length integers, then you can compute a digest for it, say using MD5, SHA1, SHA2, etc. This is certainly not bijective (because it's not injective) but is unlikely that there'll any be collisions.
Actually there is an easy way to map a vector of integers to a single integer in a bijective way. First treat numbers as strings say 0 1 00 01 10 11 .. for 0,1,2,3,4,5, ... then bijectively combine the strings a pair at a time using a method like http://bijective.dogma.net/compres8.htm The method on that page is for bytes but its easy to make it work for bits. If you can't see how to do that you and change bijectively each string to bytes. example so you want to map a vector or three integers to a single integer. Using method from that page. convert to a strings each of the three integers and then convert to bytes. DSC adds bijectively a number from 0 to N-1 to any file bijectively. For first nunber let it be ZERO then when you add the second number which you have as bytes you use N from the length of previous result it has to be at least one since its non zero. Then for third integer you combine as previous where N is the length of previous result. Its that easy. know that you have this final file you can bijectively convert to string and then that string to a number.