Created
June 17, 2016 03:09
-
-
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...
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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