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

Alma Do
  • 37,009
  • 9
  • 76
  • 105
  • http://math.stackexchange.com/questions/78363/reversible-reflexive-function-with-unique-cardinality – Henrik Feb 04 '14 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 – amit Feb 04 '14 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 – Alma Do Feb 04 '14 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. – laune Feb 04 '14 at 11:57

5 Answers5

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.

Egor Skriptunoff
  • 23,359
  • 2
  • 34
  • 64
  • This is good too. While in theory taxicab isn't unique - this will fit because I'm sure integer is much lesser than 1E18 – Alma Do Feb 04 '14 at 12:17
  • +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. – Nitzan Shaked Feb 04 '14 at 12:18
  • @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 – Alma Do Feb 04 '14 at 12:20
  • Very nice, but grows too quickly for any use at which OP hinted. – laune Feb 04 '14 at 12:54
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.

Nitzan Shaked
  • 13,460
  • 5
  • 45
  • 54
  • 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 – Alma Do Feb 04 '14 at 11:58
  • 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`. – Nitzan Shaked Feb 04 '14 at 11:59
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
Egor Skriptunoff
  • 23,359
  • 2
  • 34
  • 64
  • Could you explain more about "interleave bits" ? Also interesting - what about negative values? – Alma Do Feb 04 '14 at 12:05
  • 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. – Nitzan Shaked Feb 04 '14 at 12:07
  • 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. – Egor Skriptunoff Feb 04 '14 at 12:08
  • @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. – laune Feb 04 '14 at 12:09
  • F(0,27) = 101000101 = 325 – Egor Skriptunoff Feb 04 '14 at 12:09
  • @EgorSkriptunoff You can simply concatenate the binaries... No diff, you must set a limit for F's operands... – laune Feb 04 '14 at 12:10
  • @laune of course. That is why we either have to have a larger result type (or settle for collisions, as I proposed). – Nitzan Shaked Feb 04 '14 at 12:10
  • @laune - My method does not require numbers to be limited. It works for arbitrary long natural numbers. – Egor Skriptunoff Feb 04 '14 at 12:17
  • @EgorSkriptunoff Yes, with F being of the type "integers of unlimited precision", too. But I don't think that was OP's original idea. Your algorithm would the advantage that you don't have to know the domains for x and y beforehand and still produce a unique result. But if you (see OP's use case) need to have and array for the result... – laune Feb 04 '14 at 12:51
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
Falk Hüffner
  • 4,942
  • 19
  • 25
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

Enigmatisms
  • 115
  • 4