Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

5 Answers 5

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;
}
share|improve this answer
    
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
5  
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

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.

share|improve this answer

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$.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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