Pairing Functions

Some times you're working on a problem and you just end up working yourself into a corner with no way out. Well, there's a way out but you're too stubborn to fix it. One such corner I ran into a situation where I wanted to uniquely identify two objects based on 2 properties, both numbers. Sure you could come up with a different way to uniquely identify them but this seemed best at the time.

These were the only two properties that could change between calls (the API only returned every object, not updates) and I didn't want to compare more than I could get away with. The small issue is that map keys in ecmascript can't be an array, e.g. [1, 2].

I wanted to use a map to iterate over objects I had and add those to a map, then iterate over the next fetch of objects and remove anything from the map that is the same. What ever is left in the map is new or updated. I can't combine these two together because normal math operations won't produce a unique value for the pair for every situation.

Hopefully this illustrates it more:

// One of our existing objects

ob_a = {
  id: 1
  status: 4
  ...
  label: "some text"
}

// The only field that can change in this example is status
// We call a function to fetch updates, which returns every object again
objects = refreshObjects()


// Two elements in this new list of objects, for example
ob_a = {
  id: 1
  status: 5
  ...
  label: "some string"
}

ob_b = {
  id: 2
  status: 4
  ...
  label: "some other string"
}

// We see obj_a matches an existing object and has changed, the status is different.
// However we received another object with ID 2, and the status has changed.
// The unique combination we want of 'id' and 'status' come out to the same value if we add them or multiply them.
// Same for division and subtraction for other cases

One cool algorithm than can create a unique number given two, with the reverse order being unique, is a Cantor pairing function

The Algorithm

Here it is:

// Returns a deterministic natural number given two
function cantorPair(a, b){
    return (a + b) * (a + b + 1) / 2 + a
}

a = 3
b = 4

aPair = cantorPair(a, b)
// aPair = 31

bPair = cantorPair(b, a)
// bPair = 32

Pretty neat! There's some more space efficient paring functions too, see this SO thread for deeper analysis - https://stackoverflow.com/a/13871379