0

I have many pairs of numbers (A,B), with both numbers in the pair falling between 0 and N. As an example, let's say N=100.

I need a way to uniquely map these pairs to another number. We assume pairs of (A,A) or (B,B), etc are not valid pairs.

Since I don't care about the order, these are combinations. So the total number of such pairs should be N(N-1)/2. For this example, that means there are 4950 combinations.

However, if I were to use Cantor's algorithm, I would get numbers between 0 and 20,000. That's no good! It's even worse than permutations, which you could imagine as a table of N by N (100^2).

Because this is needed for programming, I need the produced integer number from the pair to be as small as possible while still remaining unique. I also ideally need the math to be fast and simple as this will be done many times.

Is there another pairing function I can use, or did I misunderstand something along the way? Forgive me, my math is rusty.

Tyler Shellberg
  • 145

1 Answers1

0

There are tons of different pairing functions you can use. Cantor's function is particularly useful since you don't need to know what $N$ is, but if you know $N$ beforehand there are more options.

If you do know $N$, possibly the simplest thing to consider is something like $$(a,b)\mapsto aN+b.$$ This is essentially a lexicographic ordering: $(0,0)$ comes first, then $(0,1)$, etc. up to $(0,N-1)$, and then $(1,0)$, $(1,1)$, et cetera. This does depend on order, so one thing you could do is $$(a,b)\mapsto \min(a,b)N+\max(a,b);$$ this misses some numbers, but the calculations are quite simple.

Another thing you can do is just sort the pairs: order $$(0,1),(0,2),\dots,(0,N-1),(1,2),(1,3),\dots,(1,N-1),\dots,(N-2,N-1),(N-2,N),(N-1,N).$$ This bijects your pairs to the numbers in the interval $\left[0,\frac{N(N-1)}{2}\right),$ so it doesn't use any "extra" numbers. It's not immediately obvious, but this function can be represented as $$\frac{a(2N-1-a)}{2}+b-a-1;$$ there might be a few ways to speed up this computation. In general, though, I'd imagine it's better to use something like $\min(a,b)N+\max(a,b)$; using numbers that are twice as big is probably not that much of an issue, and it's also easily invertible.

Carl Schildkraut
  • 32,931
  • Thank you. The reason larger numbers might be problematic is that I'll be allocating storage for all combinations and need a quick way to map into that storage. So 2x higher max number means 2x storage cost. I am confused about something with the approach you listed though. For example, if I try the pair 99,98 I would get (99(200+1-99))/2 + 98 - 99 - 1 = 5047, which is larger than the total number of combinations, 4950. Maybe I missed something since I'm thinking 0-indexed. – Tyler Shellberg Feb 03 '21 at 21:52
  • Also: To clarify, for that last formula, you would need to sort A,B right? I'm not positive I follow what you meant by "sorting the pairs". – Tyler Shellberg Feb 03 '21 at 21:59
  • @TylerShellberg Yeah, for the $\frac{a(2N+1-a)}2+b-a-1$ formula, we're assuming $a<b$. By "sort the pairs," I mean place all the pairs $(a,b)$ with $a<b$ in lexicographic order; that's the $(0,1),(0,2),\dots,(N-2,N),(N-1,N)$ line. – Carl Schildkraut Feb 03 '21 at 22:03
  • Is it possible to change this to fit within n(n-1)/2? (Where we assume (A,A) isn't a valid pairing) – Tyler Shellberg Feb 03 '21 at 22:23
  • @TylerShellberg It does fit within $\frac{N(N-1)}2$ if your inputs satisfy $a<b$, I believe. – Carl Schildkraut Feb 03 '21 at 22:53
  • 100(100-1)/2 = 4950. If I were to do A=98, B=99, I would get back 98(200+1-98)/2 + 99 - 98 - 1, which is 5047. – Tyler Shellberg Feb 03 '21 at 22:58
  • 1
    @TylerShellberg Oh no -- I made a typo. It's supposed to be a $2N-1-a$ in the numerator, not a $2N+1-a$. This way it runs from $0$ to $\frac{N(N-1)}2-1$ inclusive. – Carl Schildkraut Feb 03 '21 at 23:23