1

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?

  • 1
    lack of research effort in this question feels pretty appalling. Just entering its title in Google search brings a bunch of results, including Stack Overflow and Math.SE... – gnat Oct 21 '14 at 12:21
  • @gnat Actually, that "suggested formula" of his is most probably from that exact answer. – Euphoric Oct 21 '14 at 12:22
  • 1
    I need a formula which works no matter the order of the numbers. This formula fails when you swap the places of A and B. I need to come up always with the same number no matter f(A,B) or f(B,A). – Placeholder Oct 21 '14 at 12:25
5

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

  • 1
    It would be easy if he "concatenated" the bits. Two 32bit numbers would give you one 64bit number. No need to play around with strings. – Euphoric Oct 21 '14 at 12:20
  • 2
    I don't really think just concatenating strings would work, since each user yields his own integer ID first, and then the one of the partner. That way for each user, the string will start always with his own integer ID. – Placeholder Oct 21 '14 at 12:22
  • This is what I was about to suggest but instead of strings I would use zero-padded binary representation. Note that you also have to always concatenate the IDs in some known order (smaller first for example) to ensure that 23-20 and 20-23 yield same result. – Muton Oct 21 '14 at 12:25
4

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.

0

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: enter image description here

  • Just as a side note, after all those months of this post. I have a degree in math but I am not a mathematician. I don't like math at all. But I use it when it is useful. I strongly oppose the idea "that everything can be expressed with math". No, it can't. Thanks to all the "great mathematicians" which joined to help to "resolve" this question. This very simple - to the point of stupidity - formula is now supporting a real live system for medical purposes. And it works great. – Placeholder Feb 4 '15 at 14:49
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.