Generate unique integer from two integers with algorithm

Question

I am currently trying to come up with an algoritm which would take at least two numbers (say user IDs) and then come up with an unique number which is generated based on these two numbers. Each integer can be as big as an INT(11) in a Database (a number with 11 digits)

Example: User A (with ID:23, would like to interact with user B (ID: 20) and an unique number out of those two numbers must be generated, say 4094. This number might or might not be reversible back to 23 and 20 (I don't really care) but it's important only these two numbers to always produce this same number. It is very important no matter of the order (23-20, or 20-23) the generated number to be still the same too).

• I was thinking it would be just easier to use some hashing function (SHA2, since MD5 allows collisions).
• I also checked the suggested formula of:

π(a,b)=12(a+b)(a+b+1)+b

but it does not work when you swap A and B.

• I know this can be done by a database table, which stores the relation between the two tables but I want to avoid this by doing it in the runtime.

Do you have any good ideas for a single math formula which would do the trick for me?

Answer 1

It's easy to come up with a scheme, but you need a number range that is at least as big as the square of the possible number range for ids. Otherwise you cannot guarantee what you need, i.e. that the combined value is unique (google "pigeonhole principle"). This probably means that you need a bigger data type to store the combined number than for the id.

The actual solution is easy: simply format both numbers up to a fixed width and concatenate them. For instance, 35 and 534 would yield 000534000035, which equates to 534000035. It's tempting to try to build a more "efficient" scheme, but since that can't work, per the pigeonhole principle, you might as well do the most primitive thing imaginable.

Edit: I missed your requirement that the mapping must be symmetrical. For that, you must sort the two numbers consistently first.

(Note that unless you absolutely, positively have to use a numeric combined handle, it is almost certainly much easier to generate a combined string instead.)

Answer 2

If only problem is that you want the two numbers to be interchangeable, then just sort them. Make it so bigger number is always first and smaller second. Then you can use the Pairing Function you already tried.

Answer 3

I have modified the original Cantor's formula for pairs:

pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + k2

To this custom one:

pi(k1, k2) = 1/2(k1 + k2)(k1 + k2 + 1) + (k1*k2)

So far all unique numbers, no matter f(A,B) or f(A,B). If anyone can improve the algorithm, you are welcome, I am not that good at math calculations and progression.

Here's a sample result:

Answer 4

I might be a bit late, but if you assign a unique prime number to a and b, multiplying all the prime numbers will result in a unique sum.

if p(x) = the x'th prime number, so p(0) = 2 and p(1) = 3, then p(a) * p(b) = p(b) * p(a). There are no other a/b pairs that will result in the same thing.

This also has the added perk of working for any number of variables.

Answer 5

I have used your formula only 12*(a+b)*(a+b+1)+b and sorting it with greater number first atatching python code here for refernce, im gonna use in java that.

def gen(a,b):
    if(a<b):
        a,b=b,a
    return 12*(a+b)*(a+b+1)+b
print(gen(13,21))