# Bijection: tree-like lists - natural numbers [duplicate]

We define a tree-like list, or trist for short, as the empty list or a list containing only previously constructed trists.

The natural numbers can either include 0 or not, according to your preference.

The task is to create a pair of functions or complete programs f and g (they don't have to be named like this or even named at all) that implement a bijection between trists and the natural numbers. In other words:

• f must be able to turn any trist into a natural number

• g must be able to turn any natural number into a trist

• f(g(n)) must equal n for any natural number n

• g(f(l)) must be equivalent to l for any trist l

You can assume that all arguments and results fit in the usual numeric type for your language. Alternatively, instead of the numeric type you could represent a natural number as a list of binary digits, either consistently little- or consistently big-endian.

The shortest solution per language wins. If your functions are recursive, you must name them. If your language requires a statement separator or a newline between the two functions/programs, you don't have to count it.

This is a sample algorithm in Python3 (you are free to implement the bijection in any way you like):

def f(x):
r = 0
for y in x:
r = (2 * r + 1) * 2**f(y)
return r

def g(n):
r = []
while n:
m = 0
while n % 2 == 0:
n //= 2
m += 1
n //= 2
r = [g(m)] + r
return r

tests = [
[],
[[]],
[[],[]],
[[[]],[],[[[]],[]]],
[[[[[]]]]],
]
for l in tests: print(g(f(l)) == l)

for n in range(20): print(f(g(n)) == n)


It uses the following representation:

$\begin{array}{|l} f([~])=0\\ f([a_0,a_1,\ldots,a_{n-1}])=\overline{ 1\underbrace{0\ldots0}_{f(a_0)\\\text{zeroes}}~ 1\underbrace{0\ldots0}_{f(a_1)\\\text{zeroes}}~ \ldots~ 1\underbrace{0\ldots0}_{f(a_{n-1})\\\text{zeroes}}} {}_{(2)} \end{array}$

Challenge inspired by @LeakyNun's question in chat.

• Related Jul 31, 2018 at 10:24
• The similarity to Decode the Void is striking. Duplicate indeed, and I suck at searching PPCG.
– ngn
Jul 31, 2018 at 11:13
• PPCG sucks at being searched. Jul 31, 2018 at 19:23

# Python 2, 11811410910510397 94 bytes

f=lambda x:x>[]and f(x[:-1])*2+1<<f(x[-1])
g=lambda n:[g(len(w))for w in bin(n).split('1')[1:]]


Try it online!

Same encoding as the example...

• @Lynn, it seems i can remove n and and it still works Jul 31, 2018 at 10:44
• @TFeld I'm afraid this meta implies that f= and g= should be counted. Sorry for the confusion. You can still omit the newline, as I intended the byte count to be the sum of two separate functions/programs.
– ngn
Jul 31, 2018 at 10:51
• @ngn, No problem, I've counted them in my counts already (and omitted the newline) Jul 31, 2018 at 10:52