Mapping two integers to one in a unique and deterministic way

Question

Imagine two positive integers A and B  I want to combine these two into a single integer C    There can be no other integers D and E which combine to C  So combining them with the addition operator doesn t work  Eg 30   10   40   40   0   39   1 Neither does concatination work  Eg  31     2    312    3     12   This combination operation should also be deterministic  always yield the same result with the same inputs  and should always yield an integer on either the positive or the negative side of integers

User · Answer

let us have two number B and C    encoding  them into single number A   A   B   C   N  where  B A   N   B  C A   N   C

User · Answer

What you suggest is impossible  You will always have collisions   In order to map two objects to another single set  the mapped set must have a minimum size of the number of combinations expected   Assuming a 32-bit integer  you have 2147483647 positive integers  Choosing two of these where order doesn t matter and with repetition yields 2305843008139952128 combinations  This does not fit nicely in the set of 32-bit integers   You can  however fit this mapping in 61 bits  Using a 64-bit integer is probably easiest  Set the high word to the smaller integer and the low word to the larger one

User · Answer

You re looking for a bijective NxN - gt  N mapping  These are used for e g  dovetailing  Have a look at this PDF for an introduction to so-called pairing functions  Wikipedia introduces a specific pairing function  namely the Cantor pairing function     Three remarks    As others have made clear  if you plan to implement a pairing function  you may soon find you need arbitrarily large integers  bignums   If you don t want to make a distinction between the pairs  a  b  and  b  a   then sort a and b before applying the pairing function  Actually I lied  You are looking for a bijective ZxZ - gt  N mapping  Cantor s function only works on non-negative numbers  This is not a problem however  because it s easy to define a bijection f   Z - gt  N  like so    f n    n   2 if n    0 f n    -n   2 - 1 if n  lt  0

User · Answer

How about something much simpler  Given two numbers  A and B let str be the concatenation   A           B   Then let the output be hash str   I know that this is not a mathematical answer  but a simple python  which has an in built hash function  script should do the job

User · Answer

We can encode two numbers into one in O 1  space and O N  time  Suppose you want to encode numbers in the range 0-9 into one  eg  5 and 6  How to do it  Simple    5 10   6   56           5 can be obtained by doing 56 10      6 can be obtained by doing 56 10   Even for two digit integer let s say 56 and 45  56 100   45   5645  We can again obtain individual numbers by doing 5645 100 and 5645 100 But for an array of size n  eg  a    4 0 2 1 3   let s say we want to encode 3 and 4  so   3   5   4   19               OR         3   5   4   23  3  - 19   5   3                         3  - 23   5   3  4  - 19   5   4                         4  - 23   5   4  Upon generalising it  we get     x   n   y     OR       x   n   y  But we also need to take care of the value we changed  so it ends up as      x n  n   y  OR x   n  y n   You can obtain each number individually by dividing and finding mod of the resultant number

User · Answer

Cantor pairing function is really one of the better ones out there considering its simple  fast and space efficient  but there is something even better published at Wolfram by Matthew Szudzik  here  The limitation of Cantor pairing function  relatively  is that the range of encoded results doesn t always stay within the limits of a 2N bit integer if the inputs are two N bit integers  That is  if my inputs are two 16 bit integers ranging from 0 to 2 16 -1  then there are 2 16    2 16 -1  combinations of inputs possible  so by the obvious Pigeonhole Principle  we need an output of size at least 2 16    2 16 -1   which is equal to 2 32 - 2 16  or in other words  a map of 32 bit numbers should be feasible ideally  This may not be of little practical importance in programming world    Cantor pairing function    a   b     a   b   1    2   a  where a  b  gt   0      The mapping for two maximum most 16 bit integers  65535  65535  will be 8589803520 which as you see cannot be fit into 32 bits    Enter Szudzik s function    a  gt   b   a   a   a   b   a   b   b   where a  b  gt   0      The mapping for  65535  65535  will now be 4294967295 which as you see is a 32 bit  0 to 2 32 -1  integer  This is where this solution is ideal  it simply utilizes every single point in that space  so nothing can get more space efficient       Now considering the fact that we typically deal with the signed implementations of numbers of various sizes in languages frameworks  let s consider signed 16 bit integers ranging from - 2 15  to 2 15 -1  later we ll see how to extend even the ouput to span over signed range   Since a and b have to be positive they range from 0 to 2 15 - 1   Cantor pairing function       The mapping for two maximum most 16 bit signed integers  32767  32767  will be 2147418112 which is just short of maximum value for signed 32 bit integer    Now Szudzik s function        32767  32767     1073741823  much smaller     Let s account for negative integers  That s beyond the original question I know  but just elaborating to help future visitors   Cantor pairing function   A   a  gt   0   2   a   -2   a - 1  B   b  gt   0   2   b   -2   b - 1   A   B     A   B   1    2   A        -32768  -32768     8589803520 which is Int64  64 bit output for 16 bit inputs may be so unpardonable     Szudzik s function    A   a  gt   0   2   a   -2   a - 1  B   b  gt   0   2   b   -2   b - 1  A  gt   B   A   A   A   B   A   B   B        -32768  -32768     4294967295 which is 32 bit for unsigned range or 64 bit for signed range  but still better    Now all this while the output has always been positive  In signed world  it will be even more space saving if we could transfer half the output to negative axis  You could do it like this for Szudzik s   A   a  gt   0   2   a   -2   a - 1  B   b  gt   0   2   b   -2   b - 1  C    A  gt   B   A   A   A   B   A   B   B    2  a  lt  0  amp  amp  b  lt  0    a  gt   0  amp  amp  b  gt   0   C   -C - 1    -32768  32767    gt  -2147483648   32767  -32768    gt  -2147450880   0  0    gt  0    32767  32767    gt  2147418112   -32768  -32768    gt  2147483647   What I do  After applying a weight of 2 to the the inputs and going through the function  I then divide the ouput by two and take some of them to negative axis by multiplying by -1    See the results  for any input in the range of a signed 16 bit number  the output lies within the limits of a signed 32 bit integer which is cool  I m not sure how to go about the same way for Cantor pairing function but didn t try as much as its not as efficient  Furthermore  more calculations involved in Cantor pairing function means its slower too    Here is a C  implementation   public static long PerfectlyHashThem int a  int b        var A    ulong  a  gt   0   2    long a   -2    long a - 1       var B    ulong  b  gt   0   2    long b   -2    long b - 1       var C    long   A  gt   B   A   A   A   B   A   B   B    2       return a  lt  0  amp  amp  b  lt  0    a  gt   0  amp  amp  b  gt   0   C   -C - 1     public static int PerfectlyHashThem short a  short b        var A    uint  a  gt   0   2   a   -2   a - 1       var B    uint  b  gt   0   2   b   -2   b - 1       var C    int   A  gt   B   A   A   A   B   A   B   B    2       return a  lt  0  amp  amp  b  lt  0    a  gt   0  amp  amp  b  gt   0   C   -C - 1      Since the intermediate calculations can exceed limits of 2N signed integer  I have used 4N integer type  the last division by 2 brings back the result to 2N    The link I have provided on alternate solution nicely depicts a graph of the function utilizing every single point in space  Its amazing to see that you could uniquely encode a pair of coordinates to a single number reversibly  Magic world of numbers

User · Answer

It isn t that tough to construct a mapping       1  2  3  4  5  use this mapping if  a b      b a  1  0  1  3  6 10 2  2  4  7 11 16 3  5  8 12 17 23 4  9 13 18 24 31 5 14 19 25 32 40     1  2  3  4  5 use this mapping if  a b      b a   mirror  1  0  1  2  4  6 2  1  3  5  7 10 3  2  5  8 11 14 4  4  8 11 15 19 5  6 10 14 19 24       0  1 -1  2 -2 use this if you need negative positive  0  0  1  2  4  6  1  1  3  5  7 10 -1  2  5  8 11 14  2  4  8 11 15 19 -2  6 10 14 19 24   Figuring out how to get the value for an arbitrary a b is a little more difficult

User · Answer

Check this  http   en wikipedia org wiki Pigeonhole principle  If A  B and C are of same type  it cannot be done  If A and B are 16-bit integers  and C is 32-bit  then you can simply use shifting   The very nature of hashing algorithms is that they cannot provide a unique hash for each different input

User · Answer

Is this even possible  You are combining two integers  They both have the range -2 147 483 648 to 2 147 483 647 but you will only take the positives  That makes 2147483647 2   4 61169E 18 combinations  Since each combination has to be unique AND result in an integer  you ll need some kind of magical integer that can contain this amount of numbers     Or is my logic flawed

User · Answer

If you want more control such as allocate X bits for the first number and Y bits for the second number  you can use this code   class NumsCombiner        int num a bits size      int num b bits size       int BitsExtract int number  int k  int p                return    1  lt  lt  k  - 1   amp   number  gt  gt   p - 1            public      NumsCombiner int num a bits size  int num b bits size                this- gt num a bits size   num a bits size          this- gt num b bits size   num b bits size             int StoreAB int num a  int num b                return  num b  lt  lt  num a bits size    num a             int GetNumA int bnum                return BitsExtract bnum  num a bits size  1              int GetNumB int bnum                return BitsExtract bnum  num b bits size  num a bits size   1               I use 32 bits in total  The idea here is that if you want for example that first number will be up to 10 bits and second number will be up to 12 bits  you can do this   NumsCombiner nums mapper 10  bits for first number    12  bits for second number       Now you can store in num a the maximum number that is 2 10 - 1   1023 and in num b naximum value of 2 12 - 1   4095   To set value for num A and num B   int bnum   nums mapper StoreAB 10  value for a    12   value from b       Now bnum is all of the bits  32 bits in total  You can modify the code to use 64 bits  To get num a   int a   nums mapper GetNumA bnum     To get num b   int b   nums mapper GetNumB bnum     EDIT  bnum can be stored inside the class  I did not did it because my own needs I shared the code and hope that it will be helpful   Thanks for source  https   www geeksforgeeks org extract-k-bits-given-position-number  for function to extract bits and thanks also to mouviciel answer in this post  Using these to sources I could figure out more advanced solution

User · Answer

Given positive integers A and B  let D   number of digits A has  and E number of digits B has The result can be a concatenation of D  0  E  0  A  and B    Example  A   300  B   12  D   3  E 2 result   302030012   This takes advantage of the fact that the only number that starts with 0  is 0    Pro  Easy to encode  easy to decode  human readable  significant digits can be compared first  potential for compare without calculation  simple error checking   Cons  Size of results is an issue  But that s ok  why are we storing unbounded integers in a computer anyways

User · Answer

Although Stephan202 s answer is the only truly general one  for integers in a bounded range you can do better  For example  if your range is 0  10 000  then you can do    define RANGE MIN 0  define RANGE MAX 10000  unsigned int merge unsigned int x  unsigned int y        return  x    RANGE MAX - RANGE MIN   1     y     void split unsigned int v  unsigned int  amp x  unsigned int  amp y        x   RANGE MIN    v    RANGE MAX - RANGE MIN   1        y   RANGE MIN    v    RANGE MAX - RANGE MIN   1        Results can fit in a single integer for a range up to the square root of the integer type s cardinality  This packs slightly more efficiently than Stephan202 s more general method  It is also considerably simpler to decode  requiring no square roots  for starters

User · Answer

The standard mathematical way for positive integers is to use the uniqueness of prime factorization   f  x  y   - gt  2 x   3 y   The downside is that the image tends to span quite a large range of integers so when it comes to expressing the mapping in a computer algorithm you may have issues with choosing an appropriate type for the result   You could modify this to deal with negative x and y by encoding a flags with powers of 5 and 7 terms   e g   f  x  y   - gt  2  x    3  y    5  x lt 0    7  y lt 0

User · Answer

Here is an extension of  DoctorJ  s code to unbounded integers based on the method given by  nawfal  It can encode and decode  It works with normal arrays and numpy arrays      usr bin env python from numbers import Integral      def tuple to int tup           Return  the unique non-negative integer encoding of a tuple of non-negative integers         if len tup     0     normally do if not tup  but doesn t work with np         raise ValueError  Cannot encode empty tuple       if len tup     1          x   tup 0          if not isinstance x  Integral               raise ValueError  Can only encode integers           return x     elif len tup     2            print  len 2           x  y   tuple to int tup 0 1    tuple to int tup 1 2      Just to validate x and y          X   2   x if x  gt   0 else -2   x - 1    map x to positive integers         Y   2   y if y  gt   0 else -2   y - 1    map y to positive integers         Z    X   X   X   Y  if X  gt   Y else  X   Y   Y     encode            Map evens onto positives         if  x  gt   0 and y  gt   0               return Z    2         elif  x  lt  0 and y  gt   0 and X  gt   Y               return Z    2         elif  x  lt  0 and y  lt  0 and X  lt  Y               return Z    2           Map odds onto negative         else              return  -Z - 1     2     else          return tuple to int  tuple to int tup  2       tuple tup 2           speed up tuple tup 2          def int to tuple num  size 2           Return  the unique tuple of length  size  that encodes to  num          if not isinstance num  Integral           raise ValueError  Can only encode integers  got      format num       if not isinstance size  Integral  or size  lt  1          raise ValueError  Tuple is the wrong size       format size       if size    1          return  num       elif size    2             Mapping onto positive integers         Z   -2   num - 1 if num  lt  0 else 2   num            Reversing Pairing         s   isqrt Z          if Z - s   s  lt  s              X  Y   Z - s   s  s         else              X  Y   s  Z - s   s - s            Undoing mappint to positive integers         x    X   1     -2 if X   2 else X    2    True if X not divisible by 2         y    Y   1     -2 if Y   2 else Y    2    True if Y not divisible by 2          return x  y      else          x  y   int to tuple num  2          return int to tuple x  size - 1     y     def isqrt n            Return  the largest integer x for which x   x does not exceed n           Newton s method  via http   stackoverflow com a 15391420     x   n     y    x   1     2     while y  lt  x          x   y         y    x   n    x     2     return x

User · Answer

If A and B can be expressed with 2 bytes  you can combine them on 4 bytes  Put A on the most significant half and B on the least significant half   In C language this gives  assuming sizeof short  2 and sizeof int  4    int combine short A  short B        return A lt  lt 16   B     short getA int C        return C gt  gt 16     short getB int C        return C  amp  0xFFFF

User · Answer

For positive integers as arguments and where argument order doesn t matter    Here s an unordered pairing function    lt x  y gt    x   y   trunc   x - y  - 1  2   4     lt y  x gt   For x   y  here s a unique unordered pairing function    lt x  y gt    if x  lt  y             x    y - 1    trunc  y - x - 2  2   4           if x  gt  y              x - 1    y   trunc  x - y - 2  2   4            lt y  x gt

User · Answer

f a  b    s a b    a  where s n    n  n 1  2   This is a function -- it is deterministic   It is also injective -- f maps different values for different  a b  pairs  You can prove this using the fact  s a b 1 -s a b    a b 1  lt  a     It returns quite small values --  good if your are going to use it for array indexing  as the array does not have to be big   It is  cache-friendly -- if two  a  b  pairs are close to each other  then f maps numbers to them which are close to each other  compared to other methods     I did not understand what You mean by       should always yield an integer on   either the positive or the negative   side of integers   How can I write  greater than    less than  characters in this forum

User · Answer

Say you have a 32 bit integer  why not just move A into the first 16 bit half and B into the other   def vec pack vec       return vec 0    vec 1    65536    def vec unpack number       return  number   65536  number    65536     Other than this being as space efficient as possible and cheap to compute  a really cool side effect is that you can do vector math on the packed number   a   vec pack  2 4   b   vec pack  1 2    print vec unpack a b      3  6  Vector addition print vec unpack a-b      1  2  Vector subtraction print vec unpack a 2      4  8  Scalar multiplication

User · Answer

Let number a be the first  b the second  Let p be the a 1-th prime number  q be the b 1-th prime number  Then  the result is pq  if a lt b  or 2pq if a gt b  If a b  let it be p 2

[algorithm] Mapping two integers to one, in a unique and deterministic way

Examples related to algorithm

Examples related to mapping

Examples related to integer

Examples related to deterministic

Examples related to math