CODEWITHSUNDEEP
algorithmfunction
Alma Do
Alma Do

Reputation: 37365

Mapping function for two integers

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:

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:

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

Upvotes: 2

Views: 187

Answers (5)

Enigmatisms
Enigmatisms

Reputation: 175

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

Upvotes: 0

Falk H&#252;ffner
Falk H&#252;ffner

Reputation: 5040

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

Upvotes: 1

Egor Skriptunoff
Egor Skriptunoff

Reputation: 23767

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.

Upvotes: 4

Egor Skriptunoff
Egor Skriptunoff

Reputation: 23767

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

Upvotes: 1

Nitzan Shaked
Nitzan Shaked

Reputation: 13598

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.

Upvotes: 2

Related Questions