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.

Cedillo

You should clarify if you mean integers in software or integers in math. In software, you pick any integer type and it will have a size, so you have a finite number of them, so there is no solution (unless, of course, your input data is guaranteed to be within some range and your output can be any integer). In math see ASk's solution. – Encarnalize

I'm talking about bounded integers in a low, positive range. Say 0 to 10,000 – Cedillo

@harm: So how about just 10,001*A + B? – Terrence

I've found this PHP functions: gist.github.com/hannesl/8031402 – Penrose

If the order doesn't matter eg: (3,12) & (12,3) give the same result, i use "A+B"+"A*B" – Iodine

Same question asked later on the Math stackexchange, with the same efficient top answer: Create unique number from 2 numbers – Holm

Semi-related: interleaving the bits of two integers is one way, as in The interstice of two binary numbers (which interleaves both ways; you only need one). But doing that efficiently requires special CPU support, like clmul or x86 BMI2 instruction pdep – Holm

@Iodine - your strategy breaks down with the following pairs [(45, 43),(87,22),(91, 21)(183, 10),(252, 7),(505, 3), (1011, 1),(2023, 0)] as all will yield 2023. it does seem to work well,however, for larger u32 numbers. full credit to jean-claude-arbaut – Teran

Answer 1

You're looking for a bijective NxN -> 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 -> 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 -> N, like so:
• f(n) = n * 2 if n >= 0
• f(n) = -n * 2 - 1 if n < 0

Johnnyjohnnycake

+1 I think this is the correct answer for unbounded integers. – Mohr

How can i get again value of k1, k2 ? – Welldefined

@MinuMaster: that is described in the same Wikipedia article, under Inverting the Cantor pairing function. – Johnnyjohnnycake

See also Szudzik's function, explained by newfal below. – Asternal

While this is correct for unbounded integers, it's not best for bounded integers. I think @blue-raja's comment makes the most sense by far. – Loculus

That doesn't work for non-positive integers. Ex: (0, 0) -> 0, (-1, 0) -> 0. – Edison

Answer 2

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 >= 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 >= b ? a * a + a + b : a + b * b;  where a, b >= 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 >= 0 ? 2 * a : -2 * a - 1;
B = b >= 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 >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= 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 >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;

(-32768, 32767) => -2147483648

(32767, -32768) => -2147450880

(0, 0) => 0 

(32767, 32767) => 2147418112

(-32768, -32768) => 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 >= 0 ? 2 * (long)a : -2 * (long)a - 1);
    var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
    var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

public static int PerfectlyHashThem(short a, short b)
{
    var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
    var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 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!!

Gook

What would be the modified unhash function for signed integers? – Millrace

This answer confuses me. If you want to map (0,0) thru (65535,65535) to a single number, then a<<16 + b is better in basically every way (faster, simpler, easier to understand, more obvious). If you want (-32768,-32768) to (327687,327687) instead, just subject 32768 first. – Terrence

@BlueRaja-DannyPflughoeft you're right. My answer would be valid if range is not limited or unknown. I will update it. I had written it before limit mattered to me. Editing this answer is long been in my mind. I will find time sometime soon. – Gook

Does Szudzik's function work for combinations or permutations. It seems to be permutations right? If I want to use for Combination can I just eliminate the IF and Else parts of the algorithm? – Sophister

Here is a Python implementation of Szudzik's function generalized to tuples of any length: gitlab.com/snippets/32559 – Melindamelinde

Your hash function PerfectlyHashThem(65535, 65535) = 8,589,803,520 = 33 bit = more than 4 byte. It's not 4294967295 as you mentioned. Btw, I agree with @BlueRaja-DannyPflughoeft, if we are gonna combine 2*32bit number to a single 64 bit, then bit moving is better – Woodie

@BlueRaja can you please explain what do you mean when you say 'just subject 32768 first.' It is a term I did not hear before, I'd love to understand what that means exactly so that shifting becomes an option for (-x,-x) – Durwin

@grumpyrodriguiz I misspelled "subtract" – Terrence

Answer 3

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):

unsigned int combine(unsigned short A, unsigned short B)
{
    return ((unsigned)A<<16) | (unsigned)B;
}

unsigned short getA(unsigned int C)
{
    return C>>16;
}

unsigned short getB(unsigned int C)
{
    return C & 0xFFFF;    // or  return (unsigned short)C;
}

Making the inputs unsigned short or uint16_t makes sure they zero-extend before you | or + them together. Otherwise negative B would set the upper bits to all-ones with OR, or subtract one from the upper half if you ADD.

Casting (unsigned)A avoids signed overflow UB in the left shift after default promotion of narrow types to signed int. And for for wider types, it's also essential to avoid shifting out bits you to keep, like ((uint64_t)A << 32 | B, since default promotion stops at int.

The (unsigned)B cast isn't necessary; the important part is that it was unsigned short B to start with. The left hand side of the | being unsigned means this will also convert to unsigned.

You can use this with signed types, at least the getA and getB, and you can return signed int from combine, but the inputs need to zero-extend so in C you need them to be unsigned short before widening. Like ((unsigned)(unsigned short)A << 16) | (unsigned short)B

You might want to use uint16_t and uint32_t, to define the type widths to match the shift counts you're using.

Planish

combine() should return (unsigned short)(A<<16) | (unsigned short)(B); So that negative numbers can be packed properly. – Transalpine

@Transalpine A<<16 will go out of bounds. It should be return (unsigned int)(A<<16) | (unsigned short)(B); – Distance

Answer 4

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?

Janellajanelle

+1 That's what I think too (although I did the calculation saying the order of A and B don't matter) – Mehitable

Yes your logic is correct by the pigeonhole principle. Unforunately the asker did not specify if the integer is bounded or not. – Mohr

Yes, I had that afterthought too, but I thought the message is in essence the same, so I didn't bother recalcing. – Janellajanelle

Also I just realized I should pick up my chance calculation (literal translation from Dutch) textbooks again. – Janellajanelle

@Boris: Kansrekening is "probability theory". – Johnnyjohnnycake

Yes, you'll need an integer type twice as wide as the inputs if you want to handle full-range inputs. The same size output as if you just concatenated the bits of both inputs. I assume many use-cases for this have much more limited input ranges. – Holm

Answer 5

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<b, or 2pq if a>b. If a=b, let it be p^2.

Bauer

I doubt that you'd want a NP solution. – Lucais

Doesn't this produce the same result for a=5, b=14 and a=6, b=15? – Ostensorium

Two products of two different primes can't have the same result (unique prime factor decomposition) a=5, b=14 -> result is 13*47 = 611 a=6, b=15 -> result is 17*53 = 901 – Bauer

Answer 6

The standard mathematical way for positive integers is to use the uniqueness of prime factorization.

f( x, y ) -> 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 ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)

Quinquennial

The math is fine. But, as Boris says, if you want to run this as a computer program, you have to take into account the finiteness of the machine. The algorithm will work correctly for a subset of the integers representable in the relevant machine. – Celebrity

I did state this in my second paragraph. The tags on the question indicate 'algorithm', 'mathematical' and 'deterministic', not any particular language. The input range may not be limited and the environment might have an unbounded integer type 'bigint'. – Quinquennial

This would work but is also much slower than the Cantor pairing function, requiring exponentiation (of a fixed base). The 2^x part is trivial, just a left shift, but the 3^y part isn't. Even doing binary exponentiation, you need about log2(y) multiplies (by 3 so that's just an x86 lea reg, [reg + reg*2]), but it's still a loop with shifting and CMOV or branching. This doesn't appear to have any advantages over the existing alternatives, unless the actual numbers this makes happen to be interesting for some use-case. Interesting to discuss in an answer, but only about why it's suboptimal. – Holm

Answer 7

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 &x, unsigned int &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 :)

Ostracod

Is this by any chance possible for floats? – Coca

@Lukas: In general no, rounding error and precision limits make that pretty much impossible unless the floats happen to be fairly round numbers. y, the number that you'd want to recover with a slow fmod, would be "polluted" by rounding error from adding it to a much larger number, x * range. Adding a small number to a large number loses most of the precision of the smaller number. Think about how FP addition works: shift their mantissas to align them (based on exponent), then add, and truncate to the mantissa width (actually round). So you shift out many of the significant bits of y. – Holm

Answer 8

For positive integers as arguments and where argument order doesn't matter:

1. Here's an unordered pairing function:

   <x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>
   

2. For x ≠ y, here's a unique unordered pairing function:

   <x, y> = if x < y:
              x * (y - 1) + trunc((y - x - 2)^2 / 4)
            if x > y:
              (x - 1) * y + trunc((x - y - 2)^2 / 4)
          = <y, x>
   

Cynical

Answer 9

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 < 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?

Proboscis

Greater than and less than characters should work fine within backtick escapes. – Extemporary

This is equivalent to Cantor pairing function, and as such doesn't work with negative integers. – Cirro

Answer 10

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 >= 0 else -2 * x - 1  # map x to positive integers
        Y = 2 * y if y >= 0 else -2 * y - 1  # map y to positive integers
        Z = (X * X + X + Y) if X >= Y else (X + Y * Y)  # encode

        # Map evens onto positives
        if (x >= 0 and y >= 0):
            return Z // 2
        elif (x < 0 and y >= 0 and X >= Y):
            return Z // 2
        elif (x < 0 and y < 0 and X < 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 < 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 < 0 else 2 * num

        # Reversing Pairing
        s = isqrt(Z)
        if Z - s * s < 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 < x:
        x = y
        y = (x + n // x) // 2
    return x

Acetify

Answer 11

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.

Epimorphosis

Answer 12

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.

Brogle

Answer 13

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

Tol

How do you choose N to make this representation unique? If you solve that problem, how is this answer different from the ones above? – Cw

You should add that N must be greater than both B and C. – Shawanda

This is a worse less-detailed version of bdonlan's answer, posted 4 years later, for the special case where RANGE_MIN = 0. – Holm

The modulo encoding is the most space efficient one, let max_b = max(b) +1, then N = a * max_b + b, now that a = N / max_b, b = N % max_b – Click

Answer 14

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.

Mehitable

Answer 15

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.

Trantrance

but (8,11) and (81,1) are mapped to the same number 811 – Prepared

That is a good point. You can fix that issue by just adding a symbol in the middle. So for (8, 11) hash the string "8-11" and for (81, 1) hash the string "81-1". So in general for (A, B) hash the string "A-B". (I know it sounds hacky, but it should work). – Trantrance

its also wrong because that task is to map two integers to a new integer, not a string with a symbol – Prepared

I am coming from a CS perspective rather than a mathematical one (for mathematical solutions look at above responses). I am taking two integers, making them into a string, when then is turned into an integer. Essentially, yes I am mapping two integers to a new one. – Trantrance

This would work, but looks significantly slower than the simple Cantor formula. It's cheaper than one int->string, more like the same cost of getting the low decimal digit of one number. So this isn't simpler computationally. (And it's not invertible to recover the two numbers, which is useful in some cases.) The hash function also isn't guaranteed not to collide, although a good one hopefully won't if you're lucky for a good range of input numbers; you should test is over a range like 16-bit A and B. (nested loops over 0..65535, add results to a set and look for duplicate elements.) – Holm

Answer 16

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

Crannog

Answer 17

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 << k) - 1) & (number >> (p - 1)));
    }

public:
    NumsCombiner(int num_a_bits_size, int num_b_bits_size)
    {
        this->num_a_bits_size = num_a_bits_size;
        this->num_b_bits_size = num_b_bits_size;
    }

    int StoreAB(int num_a, int num_b)
    {
        return (num_b << 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

Divinity

Answer 18

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.

Wehrle

Answer 19

For newcomers, I would like to add to @nawfal's brilliant answer by pointing to the following reference (equation 2.1 there):

The Rosenberg-Strong Pairing Function

The mathematical formulation is the following: given a, b two nonnegative integers, we are interested in a function f such that f(a, b) = f(a', b') ==> a=a', b=b'.

The above references provide a Rosenberg-Strong function $f$ defined as follows:

f(a, b) = (max(a,b))^2 + max(a, b) + a - b

This looks more economical than Cantor's and Szudzik's (check out Figure 2 in the reference to see how the encoding works! The enumeration looks optimal).

Note that Szudzik wrote this paper but did not put his own elegant solution in this paper.

Onstad

Answer 20

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.

Varick

Answer 21

To combine two non-negative integers of any size into one, you can simply interleave their digits.

Example: 12345 and 678:

1 2 3 4 5
     6 7 8
----------
1020364758

The result is 1020364758.

You can do this with any base (e.g. base 2 or base 16). The result will be at most twice as big as the biggest number, which means that e.g. combining two 16-bit numbers will always fit in 32-bit.

If we wanted to also allow negative integers, we could encode one or both by multiplying the absolute value by 2, and then adding 1 if the number was negative. When decoding, the modulus of 2 would then indicate the sign.

We can extend this approach to decimals, for example if we wanted to combine 1234.5 and 6.78:

1 2 3 4 .5
       6. 7 8
-------- ----
10203046.5708

The result is 10203046.5708. (This is probably not very useful in programming, unless you use fixed-point numbers.)

Note how we take advantage that leading zeroes are insignificant in the integer part in the same way that trailing zeroes are insignificant in the fractional part.

Schertz