Mapping two integers to one (with an upperbound)

Question

I'm looking for a function that maps two (positive) integers into a single new integer, which can be reversed to the original combination. The question has been asked before, for example Mapping two integers to one, in a unique and deterministic way. The difference is that one of the integers is bound to an upper bound which is quite small, for example 50. The other integer is unbound.

What i'm trying to solve is that I have and 1-50 arrays with numbers 1 - max int (but mostly < 10.000.000).

array1 {1,2,3,4,5,6,7..N)  
array2 {1,2,3,4,5,6,7..N)  
array50 {1,2,3,4,5,6,7..N)  

Now I want to create a single new array which combines these N arrays to a single new array, where each number is reversable to the original array. So I thought about creating pairs, one number pointing to the array and one to the actual number in the array.

If I use the default functions like Cantor Pairing Function I get huge numbers very fast, and i'm trying to keep those numbers as small as possible. It would be preferably if the biggest part would just fit in a Int32 instead of a long. I think it should be possible because one of the numbers in my pair is bounded by 50, but I can't figure out how.

Answer 1

If you have two numbers

• a from 0 to a_max - 1
• b from 0 to 2³²/a_max - 1

you can combine them as

x = a + a_max*b;

and the combined number x will fit into a 32 bit unsigned integer.

To decode them, use

a = x%a_max;
b = x/a_max;

---

^{It is not possible to find a more efficient packing, because every possible output value is used. (There are no 'gaps' in the output.) If the bounds for b are too narrow, a larger output type must be used.}