Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given two integers, $a$ and $b$, I need an operation to produce a third number $c$. This number does not have to be an integer. The restrictions are as follows:

  1. $c$ must be unique for the inputs (but it does not have to be reversible).
  2. $a$ and $b$ must be interchangeable ($a$ & $b$ = $b$ & $a$)

Initially, the first thing I thought of was simply $a+b$, however naturally that does not fit restriction 1. Then I considered a hash function of some sort, but that doesn't fit 2.

Any thoughts?

share|improve this question
2  
What do you mean that doesn't fit 1, there is only one unique number which is the sum of a and b. –  Adam Hughes Jul 30 at 18:08
5  
I believe that the OP wants an injective operation from $\mathbb Z \times \mathbb Z$ to $\mathbb Z$ as condition 1, and for the operation to be commutative for condition 2. –  qaphla Jul 30 at 18:08
3  
@qaphla Almost, except it should be $2$-to-$1$, since $f(a, b) = f(b, a)$. –  user61527 Jul 30 at 18:09
4  
It's impossible to have such an injection from ordered pairs, but an injection from two-element subsets is fine, since then the 'commutativity' condition is implied -- $f(\{a,b\}) = f(\{b,a\})$. –  qaphla Jul 30 at 18:14
3  
I'd say that a commutative function on ordered pairs can be pretty clearly identified with a function on sets of size two, and the difference between the two isn't worth caring about. –  qaphla Jul 30 at 18:31

15 Answers 15

up vote 25 down vote accepted

If we restrict $a,b$ to be non-negative integers, we can try $f(a,b) = \dfrac{\max(a,b)(\max(a,b)+1)}{2}+\min(a,b)$.

This satisfies $f(a,b) = f(b,a)$ and grows quadratically with $\max(a,b)$. To help you see the pattern:

$f(0,0) = 0$,

$f(1,0) = 1$, $f(1,1) = 2$,

$f(2,0) = 3$, $f(2,1) = 4$, $f(2,2) = 5$,

$f(3,0) = 6$, $f(3,1) = 7$, $f(3,2) = 8$, $f(3,3) = 9$,

...

If you want to allow any integers $a,b$ then let $g$ be your favorite bijection from $\mathbb{Z}$ to $\mathbb{N}_0$, then let $f(a,b) = \dfrac{\max(g(a),g(b))(\max(g(a),g(b))+1)}{2}+\min(g(a),g(b))$.

One such bijection is $g(n) = \begin{cases} -2n & n \le 0 \\ 2n-1 & n \ge 1\end{cases}$.

share|improve this answer
1  
This is certainly the best solution so far from an implementation point of view. –  lemon Jul 30 at 20:18
    
Great answer - I can see this being very useful. –  Keith Jul 31 at 4:01
1  
Additionally, if you wanted $f$ to take on negative values as well as positive values, you could define $$f(a, b) = g^{-1}\left(\dfrac{\max(g(a),g(b))(\max(g(a),g(b))+1)}{2}+\min(g(a),g(b))\right)‌​.$$ –  Strants Jul 31 at 4:09
    
I should look to see if there is a $g$ that maps my answer to yours. –  robjohn Aug 1 at 15:51

How about just $2^a+2^b$? This represents the binary number with $1$s at exactly the $a$-th and $b$-th positions if $a\ne b$, and a single $1$ at the $(a+1)$-th position if $a=b$.

share|improve this answer
    
This is a better answer than mine. –  deinst Jul 30 at 18:28
2  
reversible? Using this method we get a and b from c. –  mridul Jul 30 at 19:08
2  
@mridul Any method we use is theoretically reversible (up to specifying which input is $a$ and which is $b$) because we have a uniqueness requirement - meaning from $f(a,b)$ we can extract the information $\{a,b\}$. –  Peter Woolfitt Jul 30 at 19:18
    
If we're talking about a computer, this becomes trickier as soon as $a$ or $b$ get bigger than $64$... not a great range. –  Jack M Jul 30 at 20:30
8  
@JackM The goal of this answer was to give a nice mathematical solution to the problem regardless of practicalities. For a good way to actually solve the problem on a computer, please see the other answers - say TonyK's answer, or JimmyK4542's answer. –  Peter Woolfitt Jul 30 at 20:34

I think $a\circ b=(2^a+1)(2^b+1)$ works, if I understand correctly. $a \circ b = b \circ a$ and $a$ and $b$ can be found (up to permutation) from $(2^a+1)(2^b+1)$ (assuming $a$ and $b$ are integers.)

share|improve this answer
    
Nice answer; especially since one can tell the original two numbers by glancing at the binary representation of the result. –  Clinton Curry Jul 30 at 18:19
    
-1 Mathematically elegant but this isn't practical to implement into code for large $a$ and $b$. –  lemon Jul 30 at 18:21
13  
Who said anything about practicality for code? –  deinst Jul 30 at 18:23
7  
Finding a power of 2 modulo a prime is trivial. –  deinst Jul 30 at 18:35
11  
@ozo If that's what the OP wants, then he ought to ask a more specific question. This answer perfectly fits the requirements as stated. It's ridiculous to downvote someone for not reading the OP's mind or making unwarranted assumptions from the question. –  Chris Hayes Jul 30 at 19:05

Peter Woolfitt's suggestion ($2^a + 2^b$) is the simplest so far, but it becomes extremely large for quite small values of $a$ and $b$. For a more manageable function, I suggest interleaving the binary representations of $a$ and $b$. Then the result will be no larger than $\max(a,b)^2$.

To make it commutative ($f(a,b)=f(b,a)$), you will first have to swap $a$ and $b$ if $a< b$. Then it goes something like this:

f := 1
while a != 0 or b != 0
    // Incorporate bottom bit of a
    f := 2 * f
    if a is odd then f := f + 1
    a := a/2 // Discard bottom bit of a

    // Incorporate bottom bit of b
    f := 2 * f
    if b is odd then f := f + 1
    b := b/2 // Discard bottom bit of b
wend
share|improve this answer
    
And what happens to the uppermost bits? It seems they get left out... –  abiessu Jul 30 at 18:42
    
@abiessu: No, every bit gets inspected and incorporated. That's why a and b get divided by 2. –  TonyK Jul 30 at 18:44
    
You're right, I mixed up my "negated input AND" logic and thought it would end prematurely. –  abiessu Jul 30 at 18:48
    
Oh, no! You're right! That 'and' should be an 'or'. I have fixed it now. –  TonyK Jul 30 at 18:54
1  
@ozo: Yes, you are right. I have fixed that with f:=1 instead of f:=0; perhaps it works now... –  TonyK Jul 30 at 19:19

More programmerly than mathily, use a nondigit separator, like the convenient decimal point. In this case I concat a string together then cast it to a float.

c = parseFloat(max(a,b) + '.' + min(a,b))

c will be unique and reversible for all interchangeable combinations of a and b.

so for example,

myhash(124,24) = 124.24
myhash(24,124) = 124.24

myhash(11231,26611) = 26611.11231

I think some index systems like the Dewey Decimal system and some part numbering schemes use this sort of bin-based technique.

But oops, then there is a problem if the second number ends with trailing zeros, so stringwise reverse it to preserve them:

c = parseFloat(max(a,b) + '.' + reverse(min(a,b)))

then

myhash(123,456) = 123.654
myhash(12300,4560) = 12300.0654
share|improve this answer
    
Whoops, this won't handle negative integers very well. –  Nathan Jul 30 at 20:06
    
Assuming $a$ and $b$ are of a similar size then this limits them each to about 3 significant figures (32-bit IEEE float) or 8 significant figures (64-bit IEEE float). –  lemon Jul 30 at 20:15
2  
You could encode the sign of min(a,b) in the first decimal digit (so for example myhash(2,1) = 2.01, myhash(2,-1) = 2.11). –  hvd Jul 31 at 12:24
    
@ozo That assumes they'll be stored in an IEEE floating point variable. That's a problem for the programming aspect, but not for the maths aspect. –  hvd Jul 31 at 12:26

Note: This answer is substantially the same as the one given by JimmyK4542. I am leaving it here in case some minor difference in wording helps someone understand the derivation.

If we can additionally assume that the integers are nonnegative, I believe that the following will satisfy the conditions given.

First note that commutativity can be guaranteed by sorting the elements, so without loss of generality we assume $a \geq b$. Call the given pair which has been sorted $(a_0, b_0)$. We can identify the following sequence which uniquely transforms a sorted pair $(a,b)$:

\begin{aligned} (0,0) &\rightarrow 0 \\ (1,0) &\rightarrow 1 \\ (1,1) &\rightarrow 2 \\ (2,0) &\rightarrow 3 \\ (2,1) &\rightarrow 4 \\ (2,2) &\rightarrow 5 \\ &\vdots \end{aligned}

From this it is clear that if we can compute the number of elements in this sequence which have $a < a_0$, and then add $b_0$, we have an answer that works. Let \begin{equation} N(k) = \sum_{n=0}^{k}{n} = (k)(k+1)/2 \end{equation}

Then we have a mapping \begin{equation} (a \, \& \, b) \rightarrow N(max(a,b))+min(a,b) \end{equation} which satisfies the two properties given.

As a benefit, this answer also scales only quadratically with the largest number in the pair.

share|improve this answer
    
It appears that the answer by JimmyK4542 was posted while I was typing this up. What is the proper etiquette here (I'm new)? Should I delete my answer, being that it is basically the same? –  Hunter Jul 30 at 19:58
    
The rule of thumb is: if you think that your explanation is clearer/more concise than someone else's then keep it. Otherwise, it's good etiquette to delete it. –  lemon Jul 30 at 20:20
1  
@Hunter There is not really a consensus on this issue of etiquette. Please see here and here for discussions on this topic. –  Peter Woolfitt Jul 30 at 20:46

Sort a and b ,then apply hash function.

c=hash(sort(a,b))

Here,

  1. c is unique for the inputs and not reversible.
  2. a and b are interchangeable (a & b = b & a).
share|improve this answer
2  
All hash functions have collisions, multiple inputs with the same output. So this violates requirement 1. The probability of getting a collision for two randomly chosen inputs may be very low, and so not worth worrying about in practice, but it can theoretically happen. –  David Z Jul 31 at 0:10

If you aren't bothered about $0$, how about sums of reciprocals?

$c(a,b)=\frac{1}{a} + \frac{1}{b}$

1. Uniqueness of $c$.

$c(a,b)=\frac{a+b}{ab}$

Assume $c(a,b) = c(ka,lb),\space k,l\in\mathbb Z_{\ne 0}$

$\implies \frac{a+b}{ab} = \frac{ka+lb}{kalb}$ $\implies \frac{a+b}{ka+lb} = \frac{ab}{kalb} = \frac{1}{kl}$

$\implies kl(a+b) = ka + lb \implies kl=k=l$

$\therefore k = l = 1$

2. Commutes - clearly since $+$ does.

share|improve this answer
    
1/2 + 1/6 = 1/3 + 1/3 –  kasperd Aug 2 at 12:54

Given $\max(|a|,|b|)$ and $a+b$, we can recover the unordered pair $(a,b)$ as $$ \textstyle\left(\min(a+b,0)+\max(|a|,|b|),\max(a+b,0)-\max(|a|,|b|)\right)\tag{1} $$ There are $4n+1$ unordered pairs of integers so that $\max(|a|,|b|)=n$; their sums being $$ \{-2n,-2n+1,\dots,0,\dots2n-1,2n\}\tag{2} $$ Since $$ \sum_{k=1}^n(4k+1)=2n^2+3n\tag{3} $$ we will set $$ f(a,b)=2\max(|a|,|b|)^2+\max(|a|,|b|)+a+b\tag{4} $$ Then the greatest $f(a,b)$ can be for $\max(|a|,|b|)=n$ is $$ 2n^2+n+2n=2n^2+3n\tag{5} $$ and the least it can be for $\max(|a|,|b|)=n+1$ is $$ 2(n+1)^2+(n+1)-2(n+1)=2n^2+3n+1\tag{6} $$ Therefore, the $f$ given in $(4)$ maps unordered pairs of integers to non-negative integers injectively (and incidentally, surjectively).

share|improve this answer
    
Beautiful. Looks like the best solution so far to me, since the OP apparently wants to use it as a perfect hashing function or something like that. -- There are parenthesis missing around $4k+1$ in (3). –  Hans Adler Aug 1 at 13:58
    
@HansAdler: thanks. I can see your point about the parentheses, so I have added them. However, I usually write $1+\sum\limits_{k=1}^n4k$ when I intend the other association, just to be sure. –  robjohn Aug 1 at 15:59

Let $p$ and $q$ be distinct primes, and let

$$c=\min(p^aq^b,p^bq^a)$$

In fact this generalizes to a function for $n$ interchangeable variables $a_1,\ldots,a_n$, using distinct primes $p_1\ldots,p_n$:

$$c=\min_{\pi}\{\prod_{i=1}^np_i^{a_{\pi(i)}}\}$$

where the min is taken over all permutations of $\{1,\ldots,n\}$.

(Note, the integers $a$ and $b$ need not be positive. The Fundamental Theorem of Arithmetic still guarantees that different multisets correspond to different values of $c$.)

share|improve this answer

Well, there is a rather simple way to do this using string operations:

  1. Let x = min(a,b) and y=max(a,b)
  2. Treating x and y as strings and + as the concatenation operator, let z = x + "|" + y
  3. Use your favorite string to binary/hex/decimal function to turn z into a number.

Let's look at an example. f(25,-36).

x = -36 and y = 25.

z = "-36|25".

Using a standard ASCII to Decimal converter, we get the number 4551541245053.

share|improve this answer

Since your answer need to be a integer the following simple steps should work:

  1. Sort the numbers a and b with the smallest first if a = b just put a first.
  2. Now put the first number in front of the dot and the second number behind the decimal, then append one to the end (so that if the second number ended in 0 it will now end in 01 to keep it unique)
  3. now you have a unique easily reversible number.

This method will also be reasonably memory efficient, and also ensure uniqueness (and you can easily find a given b and b given a).

share|improve this answer
    
I see two difficulties with this approach: 1) The result for numbers with trailing zeroes won't be unique (1.50 = 1.500) - this can be resolved by reversing the number behind the decimal point. 2) the question states "integers", how can this function be improved to handle negative integers while still being injective? –  waldrumpus Jul 31 at 8:51
1  
@waldrumpus, as TonyK observed when I asked much the same question of his answer, you could handle signs by encoding $a\le b$ as $ax.yr$, where $r$ is $b$ written in reverse (as you suggested) and $x,y\in\{0,1\}$ to indicate the signs of $a$ and $b$. –  Barry Cipra Jul 31 at 19:17
    
added a simple trick just append 1 to the end and it will always be unique –  Thijser Jul 31 at 19:45
    
@BarryCipra Very nice! Since this answer was the first thing to pop into my mind, I'm glad to see it improved and perfectly acceptable. –  waldrumpus Aug 1 at 7:51

Use complex numbers $u+vI$ with integer coefficients $u, v$. Let $c=a*b=(a+b)+abI$. It is easy to see that if we know $u=a+b$ and $v=ab$ then we know $a, b$. To see this consider the polynomial $x^2-ux+v$ then this has roots $a,b$.

If you want the answer to be real then you could use $(a+b)+(ab)\pi$

share|improve this answer

Yet another (and quite standard) solution is using the Cantor pairing function $\pi: \mathbb N\times\mathbb N\to \mathbb N$. It is a bijection. So now let's only find a bijection between unordered pairs ${\mathbb N}\choose{2}$ and ordered pairs $\mathbb N\times \mathbb N$. One such is $$\sigma:\{a,b\}\mapsto(\min\{a,b\},\max\{a,b\}-\min\{a,b\})$$ with the inverse $$\sigma^{-1}:(x,y)\mapsto \{x,x+y\}.$$

Therefore $\pi\circ\sigma$ satisfies your requirements, moreover, it is a bijection between unordered pairs of natural numbers and natural numbers, so it's efficient.

If you need integers instead of natural numbers, use your favourite bijection $\mathbb Z\to\mathbb N$, there's plenty of them.

share|improve this answer

Since some seem to be talking about programming and this is too long for a comment, I'll post this answer even though it's not really appropriate for a mathematics question. Given two 16 bit signed ints a and b, you can sort them and or them together. Meaning:

int uniqueCombo(int a, int b) { //assuming -2^15<=a,b<=2^15-1
    if(a<b)
        return (a&0xFFFF)|(b<<16);
    else
        return (b&0xFFFF)|(a<<16);
}

This, by the magic of signed and unsigned integers, unless I'm mistaken, will handle positives and negatives perfectly fine and is easy to invert (to get a as a 32 bit signed int, take out the first sixteen bits. If the biggest place digit is a one, pad the new 16 large place digits with ones. Else zeros.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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