Given two integers $n$ and $m$ (assuming for both $0 < n < 1000000$) is there some function $f$ so that if I know $f(n, m) = x$ I can determine $n$ and $m$, given $x$? Order is important, so $f(n, m) \not= f(m,n)$ (unless $n=m$).
Is it possible to combine two integers in such a way that you can always take them apart later?
-
3It rather depends what you want to achieve. It is certainly possible because $\mathbb Z \times \mathbb Z $ is countable – 2012-07-02
-
1The most obvious such function is $f(n,m)=(n,m)$. Or do you want the function to output integers or something? – 2012-07-02
-
4Google "pairing function". This is a duplicate of many prior questions. – 2012-07-02
-
2@BillDubuque This is one of those cases where as soon as I knew what the term was, I'd have my answer. But, of course, I didn't. – 2012-07-02
-
0Looks like there is a programming version of this same question on StackExchange: http://stackoverflow.com/questions/919612/mapping-two-integers-to-one-in-a-unique-and-deterministic-way – 2012-07-02
-
0@ChrisEagle yes, the goal was integers as output. – 2012-07-02
5 Answers
f(m,n) = m +(1/n)
If there are numbers to the right of the decimal,
m =number to the left of decimal.
n = the reciprocal of the numbers to the right of the decimal
example
f(m,n) =10.5 then m =10, n=1/(0.5) =2
If there are no numbers to right of the decimal [f(m,n) is itself an integer]
then m = f(m,n) -1,
n =1
example
f(m,n) =20 then m=19, n =1
$f(n,m) = 2^n 3^m$.
Alternatively, use the bijection between $\mathbb N \times \mathbb N$ and $\mathbb N$ which is given by $$f(n,m) = \frac{(n+m)(n+m+1)}{2} + m$$
-
3The advantage the $2^n 3^m$ approach has over all the other suggestions so far is that it gives you a way of encoding an ordered $r$-tuple without knowing in advance what $r$ is, by adding in powers of 5, 7 ... . – 2012-07-02
-
0@MarkBennet This scaling advantage is also shared by the Cantor pairing function, through recursive application. – 2012-07-02
-
1@MichaelBoratko If you have an integer given by the Cantor Pairing you cannot decode it without knowing how many iterations you have to go through. The prime product gives you this, at the cost of not being surjective, and this also means that the coded values will tend to be significantly higher for the prime product version. – 2012-07-02
-
0This is how [Godel numbering](http://en.wikipedia.org/wiki/G%C3%B6del_numbering#G.C3.B6del.27s_encoding) works, btw – 2012-07-02
-
0@MarkBennet Ah, now I understand what you meant. – 2012-07-02
Since others have answered, here is another idea - less easy to write down explicitly as a mathematical function, but easy to describe and easy to implement if you have a machine which can handle strings. Send the digits of the first number to odd positions and the digits of the other to even positions so (31, 5681) would go to 50,608,311.
-
0But this would only work if the numbers had the same number of digits, right? – 2012-07-02
-
4@JordanReiter I have deliberately used an example where the number of digits is different. – 2012-07-02
-
1This is the first answer so far that doesn't necessarily use at least one more than the maximum number of digits each integer is allowed, plus it has an infinite range and it's trivially easy to parse back out without knowing the original maximums. It also works just as well in binary as decimal. If storage is a premium - and I can't think of any other reason to do something like this - yours would be my first choice. – 2012-07-02
-
0@MarkBennet sorry, I see that now! – 2012-07-03
If there are no bounds on your integers, use the Cantor pairing function. It is pleasantly easy to compute, as are its two "inverses."
For the case where your integers are bounded by say $10^6$, you can simply concatenate the decimal expansions, padding with initial $0$'s as appropriate. Or do something similar with binary expansions. Dirt cheap to combine and uncombine, an easy string manipulation even when we allow bounds much larger than $10^6$.
-
7Of course the concatenation procedure can also be written mathematically: $f(m,n) = 10^6 m + n$. Given $f(m,n)$, you get back $m$ and $n$ as quotient and reminder when dividing by $10^6$. – 2012-07-02
Define $f(n,m) = n+1000000m$. Then $n = f(n,m) \mod 1000000$, and $m = \frac{f(n,m) - n}{1000000}$.