2

SO,

The problem

I have two integers, which are in first case, positive, and in second case - just any integers. I need to create a map function F from them to some another integer value, which will be:

  • Result should be integer value. For first case (x>0, y>0), positive integer value
  • Symmetric. That means F(x, y) = F(y, x)
  • Unique. That means F(x0, y0) = F(x1, y1) <=> (x0 = x1 ^ y0 = y1) V (y0 = x1 ^ x0 = y1)

My approach

At first glance, for positive integers we could use expression like F(x, y) = x2 + y2, but that will fail - for example, 892 + 232 = 132 + 912 As for second (common) case - that's even more complicated.

Use-case

That may be useful when dealing with some things, which supposed to be order-independent and need to be unique. For example, if we want to find cartesian product of many arrays and we want result to be unique independent of order, i.e. <x,z,y> is equal to <x,y,z>. It may be done with:

function decartProductPair($one, $two, $unique=false) { $result = []; for($i=0; $i<count($one); $i++) { for($j=0; $j<count($two); $j++) { if($unique) { if($i!=$j) { $result[$i*$i+$j*$j]=array_merge((array)$one[$i],(array)$two[$j]); // ^ // | // +----//this is the place where F(i,j) is needed } } else { $result[]=array_merge((array)$one[$i], (array)$two[$j]); } } } return array_values($result); }

Another use-case is to properly group sender and receiver in some SQL table, so that different senders/receivers will be differed while they should stay symmetric. Something like:

SELECT COUNT(1) AS message_count, sender, receiver FROM test GROUP BY -- this is the place where F(sender, receiver) is needed: sender*sender + receiver*receiver

(By posting samples I wanted to show that issue is certainly related to programming)

The question

As mentioned, the question is - what can be used as F? I want as simple F as it's possible. Keep in mind two cases:

  • Integer x>0, y>0. F(x,y) > 0
  • Any integer x, y and so any integer F(x,y) as a result

May be F isn't just an expression - but some algorithm to find desired result for any x,y (so tagging with too). However, expression is better because it's more like that it will be able to use that expression in SQL or PHP or whatever. Feel free to edit tagging because I'm not sure if two tags here is enough

Improve this question
4
  • math.stackexchange.com/questions/78363/… Commented Feb 4, 2014 at 11:52
  • Non efficient (possibly huge numbers) but correct solution is: define p_i= the ith prime number. F(i,j) = p_i*p_j Commented Feb 4, 2014 at 11:53
  • @Henrik I didn't get answer with F(x,y) = {x,y} (what is it?) - and interesting answer with left shift I've found non-applicable, because, obviously, integer overflow Commented Feb 4, 2014 at 11:57
  • What's wrong with a = max(x,y), b = obvious: (a << 16) | b ? You'll have to limit the size of x and y anyway. Commented Feb 4, 2014 at 11:57

5 Answers 5

Reset to default
4

Most simple solution: f(x,y) = x^5 + y^5
No positive integer is known which can be written as the sum of two fifth powers in more than one way.
As for now, this is unsolved math problem.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

This is good too. While in theory taxicab isn't unique - this will fit because I'm sure integer is much lesser than 1E18
+1 because this is cool and I learned something new. I think the OP wants something that he can't have, and that a solution that fits in an int (or: the same data type as the inputs). This is of course impossible, and if we forego that requirement than a better (imho) solution is what I proposed. But still: LIKE.
@NitzanShaked actually, solution with left shift will fit better because I'll be able to work with 16-bit integers (so if I'll declare maxint as 65535 I'll get my function for whole longint) - while here it's more narrow set because of 5-power usage. However, both are upvoted
Very nice, but grows too quickly for any use at which OP hinted.
2

You need a MAX_INTEGER constant, and the result will need to hold MAX_INTEGER**2 (say: be a long, if both are int's). In that case, one such function is:

f(x,y) = min(x,y)*MAX_INTEGER + max(x,y)

But I propose a different solution: use a hash function (say md5) of the string resulting from the concatenation of str(min(x,y)), a separator (say ".") and str(max(x,y)). That is:

f(x,y) = md5(str(min(x,y)) + "." + str(max(x,y)))

It is not unique, but collisions are very rare, and probably OK for most use cases. If still worried about collisions, save the actualy {x,y} along with f(x,y), and check if collisions happened.

Improve this answer

2 Comments

How can I hold something larger than maxint? Remember, this isn't just theoretical question - I need to store my result as integer value. I don't want to use md5 since result should be integer value
Not sure what language you are using, but: (1) use int for x and y, and use long for the result. Or (2) if you know in advance some kind of a threshold on your x and y values. Otherwise, use the hash. Or finally: use a bigint class that has arbitrary precision, and use int for x and y.
1

Sort input numbers and interleave their bits: 

x = 5 y = 3 Step 1. Sorting: 3, 5 Step 2. Mixing bits: 11, 101 -> 1_1_, 1_0_1 -> 11011 = 27 So, F(3, 5) = 27
Improve this answer

9 Comments

Could you explain more about "interleave bits" ? Also interesting - what about negative values?
Doesn't interleaving the bits mean you'll need a larger type to hold the result? Basically all solutions are such, so left-shifts (or multiplication as I suggest) work as well. Much as @laune said in the comments to the question.
Negative numbers may be mapped to positive before calculating f(x,y): mapping(x) = abs(x)*2+sign(x), where sign(x) is 0 or 1.
@Nitzan Shaked ++ It should be pretty obvious that the cardinality of the result domain is N*N/2 where N is the domain for F's operands.
F(0,27) = 101000101 = 325
|
1

A compact representation is x*(x+3)/2 + y*(x+1) + (y*(y-1))/2, which comes from an arrangement like this:

 x-> y 0 1 3 6 10 15 | 2 4 7 11 16 v 5 8 12 17 9 13 18 14 19 20
Improve this answer

Comments

0

According to [Stackoverflow:mapping-two-integers-to-one-in-a-unique-and-deterministic-way][1], if we symmetrize the formula we would have the following:

(x + y) * (x + y + 1) / 2 + min(x, y)

This might just work. For

(x + y) * (x + y + 1) / 2 + x

is unique, then the first formula is also unique. [1]: Mapping two integers to one, in a unique and deterministic way

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.