Codegolf - Биекция Между \$ \Mathbb N \$ И Не Более Чем \$N\$-Арными Деревьями

Фон

Связанный: теория гольфланга, которую я недавно опубликовал в TNB

Не более чем \$n\$-арные деревья представляют собой корневые деревья, в которых каждый внутренний узел имеет от 1 до \$n\$ дочерних элементов (включительно). Два дерева считаются идентичными только в том случае, если формы точно совпадают без изменения порядка дочерних элементов каждого узла. Другими словами, порядок детей слева направо имеет значение.

Например, ниже приведен пример не более чем троичного дерева (каждый узел помечен его исходящей степенью, а листья равны нулям):

     2

/ \

1   2

|  / \

3  0 1

/|\   |
0 0 0  0
 

Связанные последовательности OEIS: А006318 - количество не более чем двоичных деревьев, имеющих \$n\$ внутренних узлов, и А107708 предназначен для не более чем троичных деревьев.

Обратите внимание, что одноузловое дерево является допустимым не более чем \$n\$-арным деревом для любого значения \$n\$, поскольку оно не имеет внутренних узлов.

Испытание

Напишите функцию или программу, которая по положительному целому числу \$n\$ (1-й вход) отображает натуральное число (2-й вход) в уникальное не более чем \$n\$-арное дерево. Это должна быть биекция; каждое дерево должно иметь уникальное натуральное число, которое соответствует дереву. Для оценки учитывается только код, идущий от числа к дереву, но рекомендуется указать противоположную сторону, чтобы продемонстрировать, что это действительно биекция.

Выходной формат дерева является гибким (вложенные массивы, строковые/плоские представления массивов, включая круглые скобки или префиксную запись). Вы также можете выбрать «натуральное число», начиная с 0 или 1.

Применяются стандартные правила. Выигрывает самый короткий код в байтах.

#код-гольф #код-гольф #математика #открытая-функция

Питон 3, 107 байт

 
 
 
 
 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)
 
 
 
 
 

Попробуйте онлайн!

Натуральные значения начинаются с 0. Обратная карта:

Попробуйте онлайн!

Желе, 32 байта

Попробуйте онлайн!

Диадическая ссылка, принимающая \$n\$ в качестве правого аргумента и натуральное число в качестве левого аргумента и возвращающая вложенный список.

Здесь используется тот же алгоритм, что и Ответ @AndersKaseorg на Python (так что обязательно проголосуйте и за него!). Однако, несмотря на базу Python Jelly, перевести это было непросто. Основная функция была изменена с использования рекурсии на цикл while, за которым следует reduce , but a recursive method was preserved for the subsidiary function ( ⁴‘ßƊḢd¥ɼṪ$СḊ ¹©ṛ’ɼ⁴çƊḢɼпḊṚэƒ“” в коде Python).

Полное объяснение последует.

Питон 3, 83 байта

Попробуйте онлайн!

0 дает тривиальное дерево только с одним узлом. Остальные числа разбиваются на \$ 1 \le k \le n\$ и \$ x' \ge 0\$ по модулю; \$ k\$ используется как количество дочерних элементов корня, а десятичные цифры \$ x' \$ распределяются между этими дочерними элементами путем взятия каждой цифры \$ k \textrm{th} \$, начиная с разных нижних местах, рекурсивно применяя одну и ту же процедуру для каждого ребенка.

Обратный:

Попробуйте онлайн!