Перечислять двоичные деревья

Бинарные деревья

Бинарное дерево - это дерево с узлами трех типов:

• терминальные узлы, которые не имеют детей
• унарные узлы, каждый из которых имеет одного ребенка
• двоичные узлы, каждый из которых имеет двоих детей

Мы можем представить их с помощью следующей грамматики, приведенной в BNF (форма Бэкуса – Наура):

<e> ::= 
      <terminal>   
    | <unary>
    | <binary>

<terminal> ::= 
    "0"

<unary> ::= 
    "(1" <e> ")"

<binary> ::= 
    "(2" <e> " " <e> ")"

В этой грамматике узлы даны в предзаказе, и каждый узел представлен цифрой, которая является числом дочерних элементов, которые у него есть.

Числа Моцкина

Числа Моцкина ( OEIS ) ( Википедия ) имеют много интерпретаций, но одна интерпретация состоит в том, что nчисло Моцкина является числом различных двоичных деревьев с nузлами. Таблица чисел Моцкина начинается

N          Motzkin number M(N)
1          1
2          1
3          2 
4          4 
5          9 
6         21 
7         51 
8        127 
    ...

например M(5), 9, и девять различных двоичных деревьев с 5 узлами

1      (1 (1 (1 (1 0))))  
2      (1 (1 (2 0 0)))  
3      (1 (2 0 (1 0)))  
4      (1 (2 (1 0) 0))  
5      (2 0 (1 (1 0)))  
6      (2 0 (2 0 0))  
7      (2 (1 0) (1 0))  
8      (2 (1 (1 0)) 0)  
9      (2 (2 0 0) 0)  

задача

Возьмите одно положительное целое число в nкачестве входных данных и выведите все отдельные двоичные деревья с nузлами.

Примеры nот 1 до 5 с круглыми скобками для удобства чтения

0

(1 0)

(1 (1 0))
(2 0 0)

(1 (1 (1 0)))
(1 (2 0 0))
(2 0 (1 0))
(2 (1 0) 0)

(1 (1 (1 (1 0))))
(1 (1 (2 0 0)))
(1 (2 0 (1 0)))
(1 (2 (1 0) 0))
(2 0 (1 (1 0)))
(2 0 (2 0 0))
(2 (1 0) (1 0))
(2 (1 (1 0)) 0)
(2 (2 0 0) 0)

вход

На входе будет одно положительное целое число.

Выход

Выходными данными должно быть понятное представление отдельных двоичных деревьев с таким количеством узлов. Не обязательно использовать точную строку, заданную грамматикой BNF выше: достаточно, чтобы используемый синтаксис давал однозначное представление деревьев. Например, вы можете использовать []вместо (), дополнительный уровень скобок [[]]вместо [], внешние скобки присутствуют или отсутствуют, дополнительные запятые или без запятых, дополнительные пробелы, круглые скобки или без круглых скобок и т. Д.

Все они эквивалентны:

(1 (2 (1 0) 0))  
[1 [2 [1 0] 0]]  
1 2 1 0 0  
12100  
(1 [2 (1 0) 0])  
.:.--  
*%*55  
(- (+ (- 1) 1))
-+-11

Также вариант, заданный @xnor в комментарии. Поскольку существует способ перевести это в формат, который можно понять, это приемлемо.

[[[]][]]  is (2 (1 0) 0)

Чтобы сделать это легче понять , преобразовать некоторые из []в ()нравится так

[([])()]

Теперь, если вы начнете с

[]

затем вставьте двоичный файл, который нуждается в двух выражениях, которые вы получите

 [()()] which is 2

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

 [([])()] which is 21

но так как внутренняя скобка []или ()без нее может представлять 0, который не нуждается в дополнительных выражениях, вы можете интерпретировать его как

 2100

Обратите внимание, что ответы должны работать теоретически с бесконечной памятью, но, очевидно, не хватит памяти для конечного ввода, зависящего от реализации.

Вариации выхода

BNF             xnor       Christian   Ben
b(t, b(t, t))   [{}{{}{}}] (0(00))     (1, -1, 1, -1)                         
b(t, u(u(t)))   [{}{(())}] (0((0)))    (1, -1, 0, 0)           
b(u(t), u(t))   [{()}{()}] ((0)(0))    (1, 0, -1, 0)                     
b(b(t, t), t)   [{{}{}}{}] ((00)0)     (1, 1, -1, -1)              
b(u(u(t)), t)   [{(())}{}] (((0))0)    (1, 0, 0, -1)                          
u(b(t, u(t)))   [({}{()})] ((0(0)))    (0, 1, -1, 0)                          
u(b(u(t), t))   [({()}{})] (((0)0))    (0, 1, 0, -1)                        
u(u(b(t, t)))   [(({}{}))] (((00)))    (0, 0, 1, -1)                          
u(u(u(u(t))))   [(((())))] ((((0))))   (0, 0, 0, 0)  

Возможное место, чтобы проверить на дубликаты деревьев

Одно место, чтобы проверить наличие дубликата - с помощью M (5).
Это одно дерево было сгенерировано дважды для M (5) из M (4) деревьев

(2 (1 0) (1 0))  

первый, добавив унарную ветвь к

(2 (1 0) 0)

и во-вторых, добавив унарную ветвь к

(2 0 (1 0))

Понимание БНФ

БНФ состоит из простых правил:

<symbol> ::= expression

где слева это имя символа окружения <>.
Справа - выражение для построения символа. Некоторые правила используют другие правила в конструкции, например

<e> ::= <terminal>

e может быть terminal

и некоторые правила имеют символы, которые используются при построении символа, например

<terminal> ::= "0"

terminal это просто символ ноль.

Некоторые правила имеют несколько способов их построения, например

<e> ::= 
      <terminal>   
    | <unary>
    | <binary>

An eможет быть <terminal>или a <unary>или a <binary>.

И некоторые правила представляют собой последовательность частей, например,

<unary> ::= "(1" <e> ")"

A unary- символы, (1за которыми следует то, для чего можно построить, eа затем ).

Вы всегда начинаете со стартового правила, которое для этого <e>.

Несколько простых примеров:

Самая простая последовательность просто 0. Итак, мы начнем с начального правила <e>и увидим, что есть три варианта:

  <terminal>   
| <unary>
| <binary>

так что возьмите первый <terminal>. Теперь у терминала нет выбора и он есть 0. Так заменить <terminal>с 0в <e>правилах , и вы сделали.

Тогда следующий (1 0). Начните с <e>и используйте правило, <unary>которое имеет

"(1" <e> ")"

Теперь это нужно, <e>поэтому мы возвращаемся <e>и делаем выбор одного из трех, на этот раз выбора, <terminal>который дает 0. Замена 0в (1 <e> )дает (1 0), и это заменяется на <unary>так <e>есть (1 0).

Haskell, 68 байт

t 0=[""]
t 1=["0"]
t n=['(':x++y++")"|k<-[1..n-1],x<-t k,y<-t$n-k-1]

Терминальные узлы представлены 0одинарными и двоичными узлами (e)соответственно. (ee), поэтому два трехузловых дерева заданы как (00)и ((0)).

Примеры:

*Main> t 5
["(0(00))","(0((0)))","((0)(0))","((00)0)","(((0))0)","((0(0)))","(((0)0))","(((00)))","((((0))))"]
*Main> length $ t 8
127
*Main> length $ t 15
113634 

CJam (37 байт)

0aa{_2m*2\f+1Y$f+++:e__&}qi:A*{,A=},p

Демо онлайн . Обратите внимание, что это не очень эффективно, и вы, вероятно, не хотите пытаться вычислять ввод 5онлайн.

Рассечение, чтобы следовать.

Pyth ( 24 21 19 байт)

Это основано на моем решении Python 3 .

f!|sTf<sY0._T^}1_1t

Это мой первый раз, когда я использую Pyth, так что, вероятно, он все еще пригоден для игры в гольф.

Пример , вывод, когда ввод 4:

[[1, 0, -1], [1, -1, 0], [0, 1, -1], [0, 0, 0]]

1 представляет двоичный узел, 0 представляет унарный узел, а -1 представляет терминальный узел. В конце каждого дерева есть подразумеваемый конечный узел.

Пояснение :

f!|sTf<sY0._T^}1_1t
f                    filter
             ^    t  length n-1 lists of elements
              }1_1   from [1, 0, -1]
 !|                  for when both
   sT                sum of list is 0, and
     f    ._T        for each prefix of list,
      <sY0           sum of prefix is non-negative.

брейкфак, 107 байт

,>++>-[-[<-[<-[>>[[>+<-]<]>+>[[<+>>>>>+<<<<-]>]>>++>,++++>]>[<+>-[+>>]>[<->[.<<<
<<]+[->+]+>>>]]]]<[[,<]<]<]

отформатирован:

,>++>-
[
  -
  [
    <-
    [
      <-
      [
        >>
        [[>+<-]<]
        >+>
        [[<+> >>>>+<<<<-]>]
        >>++>,++++>
      ]
      >
      [
        <+>-
        [
          +>>
        ]
        >
        [
          <->[.<<<<<]
          +[->+]
          +>>>
        ]
      ]
    ]
  ]
  <
  [
    [,<]
    <
  ]
  <
]

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

Входные данные принимаются в виде байта , а дерево 12100представляется как \x01\x02\x03\x02: для обратного преобразования, перевода tr/\x01\x02\x03/012/, обращения строки и добавления финала 0. Деревья разделены \xfe. (Вывод можно сделать более простым для чтения, например, изменив первый -на -36и .на +47.-47, где -36означает строку из 36 -символов и т. Д.)

Этот подход использует свойство (которое также использовал Бен Франкель): рассмотрение возможных узлов -1, 0, 1и игнорирование конечного-1 узел, список представляет действительное дерево тогда и только тогда, когда (1) все префиксы списка имеют неотрицательную сумму, и (2) сумма всего списка равна 0. Первое условие сохраняется при создании промежуточных узлов, поэтому в конце необходимо проверить только второе условие.

Лента делится на 5-узловые ячейки,

i d x 0 0

где iиндекс (по убыванию слева направо),d частичная сумма и xэлемент.

Эскиз потока управления:

take n and push initial node
while stack is non-empty:
    if rightmost node can be decremented:
        decrement rightmost node
        if there are less than n nodes:
            push new node
        else if valid tree:
            print
    else:
        backtrack (pop)

Обратите внимание, что иногда значение сохраняется или инициализируется как одно или два больше фактического (концептуального) значения и корректируется по мере необходимости.

Python 3 ( 138 134 128 121 119 байт)

from itertools import*
lambda n:[any(sum(t[:k])<0for k in range(n))|sum(t)or print(t)for t in product(*[[-1,0,1]]*~-n)]

Пример вывода для n=5:

(0, 0, 0, 0)
(0, 0, 1, -1)
(0, 1, -1, 0)
(0, 1, 0, -1)
(1, -1, 0, 0)
(1, -1, 1, -1)
(1, 0, -1, 0)
(1, 0, 0, -1)
(1, 1, -1, -1)

1 представляет двоичный узел, 0 представляет унарный узел, а -1 представляет терминальный узел. В конце каждого дерева есть подразумеваемый конечный узел.

Программа начинает занимать слишком много времени n=17.

JavaScript (Firefox 30-57), 79 байт

f=(m,l=0)=>m?[for(n of[1,0,-1])if(l>n&l<=m+n)for(a of f(m-1,l-n))[...a,n]]:[[]]

Где -1представляет терминал, 0унарный узел и 1двоичный узел. m=14На моем ПК начинает медленно работать. Рекурсивно работает обратно с конца дерева.

• Количество неучтенных узлов l ограничено тем фактом, что в конце может быть только 1 узел.
• Тип следующего узла nограничен необходимостью иметь достаточно неучтенных узлов, чтобы быть его дочерними.

Пролог, 149 144 138 137 131 107 байт

e(L,L)-->[0].

e([_|A],L)--> 
    [1],
    e(A,L).

e([_,_|A],L)--> 
    [2],
    e(A,B), 
    e(B,L).

e(M,E):-                   
    length([_|L],M),        
    e(L,[],E,[]).           

?- e(5,S).
S = [1, 1, 1, 1, 0] ;
S = [1, 1, 2, 0, 0] ;
S = [1, 2, 0, 1, 0] ;
S = [1, 2, 1, 0, 0] ;
S = [2, 0, 1, 1, 0] ;
S = [2, 0, 2, 0, 0] ;
S = [2, 1, 0, 1, 0] ;
S = [2, 1, 1, 0, 0] ;
S = [2, 2, 0, 0, 0].

И посчитать решения

e_count(N,Count) :-
    length([_|Ls], N),
    findall(., phrase(e(Ls,[]),E), Sols),
    length(Sols, Count).

?- e_count(N,Count).
N = Count, Count = 1 ;
N = 2, Count = 1 ;
N = 3, Count = 2 ;
N = Count, Count = 4 ;
N = 5, Count = 9 ;
N = 6, Count = 21 ;
N = 7, Count = 51 ;
N = 8, Count = 127 ;
N = 9, Count = 323 ;
N = 10, Count = 835 ;
N = 11, Count = 2188 ;
N = 12, Count = 5798 ;
N = 13, Count = 15511 ;
N = 14, Count = 41835 ;
N = 15, Count = 113634 

Python, 71 байт

f=lambda n:{(a+b,)for k in range(n)for a in f(k)for b in f(n+~k)}or[()]

Это представляет деревья в виде вложенных кортежей, таких как ((((),), ()),), которые могут быть преобразованы ((())())путем удаления запятых, пробелов и внешних элементов ().

Более ранняя 76-байтовая версия:

f=lambda n:{'('+a+b+')'for k in range(n)for a in f(k)for b in f(n+~k)}or['']

CJam, 38 байт

Использует другой подход, который отвечает CJam Питера Тейлора.

3rim*{:(1\+[{1$+}*])\:(_:z#|!},

Выходной будет что-то вроде 1110120020102100. Каждое дерево представляет собой группу nцифр (где вводится nномер).

Основная идея заключается в том, что мы создаем каждую возможную последовательность цифр 0, 1и 2, а затем отфильтровать только те, которые хорошо сформированные деревья.