42
$\begingroup$

is there some way to create unique number from 2 positive integer numbers? Result must be unique even for these pairs: 2 and 30, 1 and 15, 4 and 60. In general, if I take 2 random numbers result must be unique(or with very high probability unique)

Thanks a lot

EDIT: calculation is for computer program,so computational complexity is important

  • 0
    there is no way to force to give the bounty, but bounty can be given only after some time2011-03-12

6 Answers 6

74

The sort of function you are looking for is often called a pairing function.

A standard example is the Cantor pairing function $\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}$, given by: $\pi(a,b) = \frac{1}{2}(a+b)(a+b+1) + b$.

You can find more information here: http://en.wikipedia.org/wiki/pairing_function

24

if the numbers are $a$ and $b$, take $2^a3^b$. This method works for any number of numbers (just take different primes as the bases), and all the numbers are distinct.

  • 5
    This method generates exceptionally large numbers fairly quickly. (2^1023 on it's own is 8.9885E+307). If you're using this in excel 2^1023.9 is your upper limit)2016-09-02
4

Google pairing function. As I mentioned in the similar question, there are also other pairing functions besides the well-known one due to Cantor. For example, see this "elegant" pairing function, which has the useful property that it orders many expressions by depth.

1

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

  1. Here's an unordered pairing function:

    $ = x * y + trunc(\frac{(|x - y| - 1)^2}{4}) = $

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

     = if x < y:            x * (y - 1) + trunc((y - x - 2)^2 / 4)          if x > y:            (x - 1) * y + trunc((x - y - 2)^2 / 4)        =  
  • 2
    If you look in the comments, the OP specifically notes that for their application, argument order _does_ matter.2014-03-10
1

You could try the function by Matthew Szudzik, which is given as: $a \geq b ~?~ a*a + a + b : a+b*b$

In other words: $(a,b)\mapsto \begin{cases} a^2 + a + b & \text{if } a \geq b\\ a + b^2 & \text{if } a < b \end{cases}$

I found it here, which is a similar question as this.

-1

Apologies for resurrecting this ancient question, but I've noticed that there are collisions in the results of the Cantor pairing function.

For example, I've noticed that when a and b are 0.0 and 0.0, or 0.6 and 0.0 the result is the same: 0.48.

Is this function expected to work for non-discrete numbers, or does this have something to do with the fact they the numbers are 0.0 and 0.0 in the former case?

  • 1
    The Cantor pairing function only takes natural numbers for its input. If you want to use rationals or reals you need to work harder.2018-03-20