Mapping function for two integers

Alma Do

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

Nitzan Shaked

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.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

Is there a hash function for mapping two integers to one in an unique way?

Mapping two integers to one (with an upperbound)

Mapping two integers to one, in a unique and deterministic way

Mapping two integers into one integer in Python 3

Getting a function to return two integers

Mapping a function on two nested objects

Mapping a single function is slower than twice mapping two separate functions?

Tensorflow - mapping python function with two parameters

Mapping an Either list to integers

Mapping of strings to integers

Bijective mapping of integers

how Write a function that print integers between two numbers

Modulo Multiplication Function: Multiplying two integers under a modulus

How to properly write a function that adds two integers in C

How to code a function to print 'equal' if two integers are equal and if not, it will not print anything?

apply map function requiring two integers to a list of lists

Recursive Function that divides two integers and returns result and remainder

What function(s) determine the max or min of two integers?

Function to determine if a range of consecutive (positive) integers can be written as the sum of two (positive) composite-relatively prime integers

How to apply function of two arguments mapping objects using MapStruct?

Haskell: mapping an Either list to integers

Mapping of bitstrings with given popcount to integers

Mapping one range of integers to another

Mapping a range of integers to a single integer

AutoMapper - mapping integers to int array

Mapping an IntEnum to a second set of integers

Using a function that finds divisors, find the greatest common divisor of any two given two positive integers

Splitting string into two integers

Reading two lines of integers