14
\$\begingroup\$

Background

Related: a golflang theory I posted in TNB a while ago

At-most-\$n\$-ary trees are rooted trees where each internal node has between 1 and \$n\$ children (inclusive). Two trees are considered identical only if the shapes exactly match without re-ordering each node's children. In other words, the left-to-right order of children matters.

For example, the following is an example of an at-most-ternary tree (each node is marked with its out-degree, the leaves being zeros):

    2
   / \
  1   2
  |  / \
  3  0 1
 /|\   |
0 0 0  0

Related OEIS sequences: A006318 is the number of at-most-binary trees having \$n\$ internal nodes, and A107708 is for at-most-ternary trees.

Note that a single-node tree is a valid at-most-\$n\$-ary tree for any value of \$n\$, since it has no internal nodes.

Challenge

Write a function or program that, given a positive integer \$n\$ (1st input), maps a natural number (2nd input) to a unique at-most-\$n\$-ary tree. It must be a bijection; every tree must have a unique natural number that maps to the tree. Only the code going from a number to a tree is considered for scoring, but it is recommended to provide the opposite side to demonstrate that it is indeed a bijection.

The output format for the tree is flexible (nested arrays, string/flat array representations including parentheses or prefix notation). You can also choose the "natural number" to start at 0 or 1.

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
8
\$\begingroup\$

Python 3, 107 bytes

def f(n,x):
 def g(m):r=y[0]%m;y[0]//=m;return[g(n+1)for i in y*r]
 y=[x-1];return x and g(n)+[f(n,*y)]or[]

Try it online!

Naturals start at 0. Inverse map:

def g(n,t):
 x=0;y=1;q=t,
 while q:*q,u=q;x+=len(u)*y;y*=n+bool(q);q+=u[::-1]
 return x

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Jelly, 32 bytes

⁴‘ßƊḢd¥ɼṪ$СḊ
¹©ṛ’ɼ⁴çƊḢɼпḊṚṭƒ“”

Try it online!

A dyadic link taking \$n\$ as the right argument and a natural number as the left argument and returning a nested list.

This uses the same algorithm as @AndersKaseorg’s Python answer (so be sure to vote that one up too!). However, despite Jelly’s Python base, this was not trivial to translate. The main function was changed from using recursion to a while loop followed by a reduce, but a recursive method was preserved for the subsidiary function (g() in the Python code).

Full explanation to follow.

\$\endgroup\$
3
\$\begingroup\$

Python 3, 83 bytes

f=lambda n,x:[f(n,int(str(~-x//n)[~i::~(x%n)][::-1]or 0))for i in range(x%n+(x>0))]

Try it online!

0 yields the trivial tree with only one node. Other numbers are broken down into \$ 1 \le k \le n\$ and \$ x' \ge 0\$ using modulo; \$ k\$ is used as the number of children of the root, and the decimal digits of \$ x' \$ are distributed among those children by taking every \$ k \textrm{th} \$ digit starting from different low places, recursively applying the same procedure for each child.

Inverse:

import itertools
def invf(n, l):
    assert type(n) == int and n > 0 and type(l) == list and len(l) <= n
    return 0 if not l else int(''.join(''.join(t) for t in itertools.zip_longest(*[str(invf(n, m))[::-1] for m in l], fillvalue='0'))[::-1]) * n + (len(l) - 1 or n)

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.