Skip to content

Instantly share code, notes, and snippets.

@ihincks
Created June 17, 2016 03:09
Show Gist options
  • Save ihincks/6a046e6bcc1e7121aa36bbb0e363c576 to your computer and use it in GitHub Desktop.
Save ihincks/6a046e6bcc1e7121aa36bbb0e363c576 to your computer and use it in GitHub Desktop.
For those times you need tuples of non-negative integers to be non-negative integers...
#!/usr/bin/python
from __future__ import division
import numpy as np
def tuple_encode(x):
"""
If x is a tuple of non-negative integers, outputs a single non-negative
integer which is unique for that tuple, based on Cantor's bijection
argument.
"""
if len(x) == 1:
return x
else:
i, j = x[0], tuple_encode(x[1:])
return int((i + j + 1) * (i + j) / 2) + i
def tuple_decode(a, n):
"""
Given the non-negative integer a, does the inverse operation of
tuple_encode, assuming the desired tuple has length n.
"""
if n == 1:
return [a]
else:
# Do not question the voodoo
b = int(np.floor((1 + np.sqrt(1 + 8 * a)) / 2) - 1)
j = int(b * (b + 3) / 2 - a)
i = int((np.sqrt(9 + 8 * (a + j))- 2 * j - 3) / 2)
return [i] + tuple_decode(j, n - 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment