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

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