Home
Blog
Posted: 09 Mar 2014
This morning, I came up with a pairing function like Cantor's, except the argument order doesn't matter.
Note: Floor should actually be trunc. Also, it only works for positive integer arguments.
For the past few days, I've been thinking about how to store each user's chats & messages.
Each user has a unique positive integer ID. And, each chat can contain many messages between two users. So, I've been considering generating each chat's ID from those of its two users. (Currently, I'm not dealing with group chats because YAGNI .)
So, I googled given two numbers calculate a unique third number and found Create unique number from 2 numbers .
It said I could use the Cantor pairing function . But, I wanted something where the argument order didn't matter and that started at 1, instead of 0.
I studied the table representing the Cantor pairing function:
I noticed the algorithm to fill the table was to start at the top-left cell with 0 and move diagonally left & down until reaching the left-most column. Then, move to the top of the next column to the right, and repeat.
To create the table I wanted, I used a similar algorithm but bounded by the diagonal where x = y, instead of x = 0.
By analyzing the table above, I noticed that <x, y> = x * y along the x = y diagonal. Same along the x = y - 1 and x = y - 2 diagonals. It changes to <x, y> = x * y + 1 along the x = y - 3 diagonal.
Noticing this pattern, let's say that <x, y> = x * y + a along the x = y + n diagonal, where n = |x - y|. Then, we can just solve for a in terms of n.
Here's the table:
By googling 1 2 4 6 9 12 16 20 25 30 36 , I found the quarter-square integer sequence , defined as floor(n^2/4). Since the table above is offset by one, a(n) = floor((n-1)^2/4).
Finally, using substitution, we get:
Later, I realized I only use this function for arguments that are unique, where x ≠ y, since I don't let a user message herself.
So, since the diagonal is where x = y, I could effectively just shift all the cells in the table above one column to the right.
Mathematically, that's the same as first subtracting 1 from the larger of the two arguments.
See the unordered pairing function on Wolfram Alpha .
See the unique unordered pairing function on Wolfram Alpha .
I also implemented this unique unordered pairing function in Ruby . Instead of using floor, I just let Ruby naturally truncate the fraction by only using integers. This is actually what I want, but floor has its own math symbol and so looks prettier. Anyway, for positive fractions (which are all that result when x & y are positive integers) floor & truncate work exactly the same.
04 Jan 2015 » Publish-Email Feature Idea
05 Jun 2014 » Gratitude
16 Mar 2014 » Learn to Code