list_bijection.dart

final big0 = BigInt.zero;
final big1 = BigInt.one;
final big2 = BigInt.two;
final big8 = BigInt.from(8);

BigInt bigSqrt(BigInt n) {
  if (n.isNegative) {
    throw ArgumentError('Square root of negative numbers is not supported');
  }
  if (n < big2) {
    return n;
  }
  BigInt newtonIteration(BigInt n, BigInt x0) {
    final x1 = ((n ~/ x0) + x0) >> 1;
    if (x0 == x1 || x0 == (x1 - big1)) {
      return x0;
    }
    return newtonIteration(n, x1);
  }

  return newtonIteration(n, n);
}

BigInt cantor(BigInt x, BigInt y) {
  return ((x + y) * (x + y + big1) ~/ big2) + y;
}

(BigInt, BigInt) cantorInverse(BigInt z) {
  final t = (bigSqrt(big8 * z + big1) - big1) >> 1;
  final x = (t * (t + big1)) >> 1;
  final y = z - x;
  return (t - y, y);
}

BigInt cantorEncode(Iterable<BigInt> i) {
  if (i.isEmpty) {
    return big0;
  }
  return cantor(i.first, cantorEncode(i.skip(1))) + big1;
}

List<BigInt> cantorDecode(BigInt n) {
  if (n == big0) {
    return [];
  }
  final (x, y) = cantorInverse(n - big1);
  return [
    x,
    ...cantorDecode(y),
  ];
}

void testcase(List<int> l) {
  final n = cantorEncode(l.map(BigInt.from));
  print('$l <=> $n');
  final l2 = cantorDecode(n);
  assert(l.length == l2.length);
  for (var i = 0; i < l.length; i++) {
    assert(BigInt.from(l[i]) == l2[i]);
  }
}

void main() {
  testcase([]);
  testcase([0]);
  testcase([1]);
  testcase([1, 2, 3]);
  testcase([123]);
  testcase([123, 456]);
  testcase([2342, 456, 123, 3, 7654]);
}