The Cantor Pairing function is a mathematical function which takes two integers and combines them into a single integer that is unique to that pair. This single integer can later be "unpaired" back into the two original, separate integers. Further information on this function can be found here and here.
The Cantor pairing function can be used to pair more than just two integers together, however this must be done in a smart manner, as the size of the output of this function can jump to astronomical levels very, very quickly, which explains why I'm using Java's BigInteger class in my code.
I've written a small utility-type class in Java which contains one method capable of recursively pairing two or more integers, and another method that can unpair a single integer back into n original integers (along with two private helper methods):
package pairing;
import java.math.BigInteger;
import java.util.Arrays;
public class CantorPair {
private CantorPair() {
}
// This method recursively pairs two or more integers into a single, unique integer
public static BigInteger pair(final BigInteger... integers) {
final int n = integers.length;
if (n == 0)
throw new IllegalArgumentException("Argument list length cannot be zero!");
final BigInteger x = integers[0];
if (n == 1)
return x;
final BigInteger y = integers[1];
// If we've only been given two integers, we can pair them together and return the result!
if (n == 2) {
final BigInteger sum = x.add(y);
return sum.add(BigInteger.ONE).multiply(sum).divide(BigInteger.TWO).add(y);
}
// I've found that using a parallel stream here reduces the computation time significantly when pairing a large number of integers
return pair(Arrays.stream(makePairs(integers)).map(CantorPair::pair).parallel().toArray(BigInteger[]::new));
}
// This method recursively unpairs an integer into [n] separate integers
public static BigInteger[] unpair(final BigInteger integer, final int n) {
if (n < 1)
throw new IllegalArgumentException("Argument list length cannot be less than one!");
if (n == 1)
return new BigInteger[]{integer};
if (n == 2) {
final BigInteger i = integer.multiply(BigInteger.valueOf(8)).add(BigInteger.ONE).sqrt()
.subtract(BigInteger.ONE)
.divide(BigInteger.TWO);
return new BigInteger[]{
i.add(BigInteger.valueOf(3)).multiply(i).divide(BigInteger.TWO).subtract(integer),
integer.subtract(i.add(BigInteger.ONE).multiply(i).divide(BigInteger.TWO))
};
}
final BigInteger[] result = new BigInteger[n];
final BigInteger[] splitIntegers = unpair(integer, 2);
final int nearestPowerOfTwo = nearestPowerOfTwo(n);
if (n == nearestPowerOfTwo) {
System.arraycopy(unpair(splitIntegers[0], n / 2), 0, result, 0, n / 2);
System.arraycopy(unpair(splitIntegers[1], n / 2), 0, result, n / 2, n / 2);
} else {
System.arraycopy(unpair(splitIntegers[0], n - (n - nearestPowerOfTwo)), 0, result, 0, (n - (n - nearestPowerOfTwo)));
System.arraycopy(unpair(splitIntegers[1], n - nearestPowerOfTwo), 0, result, (n - (n - nearestPowerOfTwo)), n - nearestPowerOfTwo);
}
return result;
}
// This method splits an array of integers into groups of two
private static BigInteger[][] makePairs(final BigInteger[] inputList) {
final BigInteger[][] result = new BigInteger[(int) Math.ceil(inputList.length / 2.0)][];
for (int i = 0; i < inputList.length; i += 2)
result[i / 2] = (i == inputList.length - 1) ? new BigInteger[]{inputList[i]} : new BigInteger[]{inputList[i], inputList[i + 1]};
return result;
}
// This method returns the nearest power of two that is less than or equal to [x]
private static int nearestPowerOfTwo(int x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x ^ (x >> 1);
}
I am quite happy with the pair method, as I have used it to pair lists of 100000+ integers nearly instantly on my machine, however the unpair method does not preform nearly as well, especially once it is tasked with unpairing large integers. The computation time for this second method is long enough that I've used a stopwatch to time it - Integer lists which take the pair method ~1 second to complete take the unpair method more than 15 seconds to unpair. I've written a small test Class below which illustrates this fact (the variable numberOfIntegersToPair can be adjusted to change how many integers are paired/unpaired):
package main;
import java.math.BigInteger;
import java.util.stream.IntStream;
import pairing.CantorPair;
public class Main {
public static void main(String[] args) {
// Around 100000 is where I really begin to notice a slowdown on my machine
// Pairing completes instantly, but unpairing takes about 16 seconds
// The time difference between the two continues to noticeably increase after this
int numberOfIntegersToPair = 100000;
// Make an array containing [numberOfIntegersToPair] integers
BigInteger[] bigIntegers = IntStream.range(0, numberOfIntegersToPair)
.mapToObj(BigInteger::valueOf)
.toArray(BigInteger[]::new);
System.out.println("Starting to pair...");
// Let's pair our integer list and store the result
BigInteger pairedIntegers = CantorPair.pair(bigIntegers);
System.out.println("Done pairing!");
System.out.println("Starting to unpair...");
// Now let's unpair our large integer back into the smaller integers that formed it
// As the [numberOfIntegersToPair] increases, this function will begin to take significantly longer to complete
BigInteger[] unpairedIntegers = CantorPair.unpair(pairedIntegers, bigIntegers.length);
System.out.println("Done unpairing!");
}
}
I've tried to optimize this code as much as I know how (parallel streams, System.arraycopy instead of manual array copys, the use of arrays over lists wherever possible, etc.), and my adjustments have helped a bit (they helped speed up the pair function a lot), but I am unable to speed up the unpair method any further on my own. Perhaps there is nothing that can be done, but I'm open to any and all suggestions.
