генерировать все двоичные деревья с n узлами OCaml

Question

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

Вот как я представляю двоичные деревья:

type 'a tree = Empty | Node of 'a * 'a tree * 'a tree

Поэтому я пытаюсь реализовать функцию all_tree : int -> tree list такую, что:

1. all_tree 0 = [Empty]
2. all_tree 1 = [Node('x',Empty,Empty)]
3. all_tree 2 = [Node('x',Node('x',Empty,Empty),Empty); Node('x',Empty,Node('x',Empty,Empty))]
4. ...

Я попробовал несколько идей, но они не сработали.Например, мы можем попробовать следующее:

let rec all_tree result = function
   |0 -> r
   |s -> all_tree ((List.map (fun i -> Node('x',i,Empty)) result)@(List.map (fun i -> Node('x',Empty,i)) result) ) (s-1)
in all_tree [Empty] (*some number*)

Этот код не работает, потому что он не генерирует все возможности.

Answer 1

Вот один из возможных ответов.

let rec all_trees = function
  | 0 -> [Empty]
  | n ->
  let result = ref [] in
  for i = 0 to n-1 do
    let left_side = all_trees i
    and right_side = all_trees (n-1-i) in
    List.iter
      (fun left_tree ->
        List.iter
          (fun right_tree ->
            result := (Node('x', left_tree, right_tree)) :: (!result)
          )
          right_side
      )
      left_side
  done;
  !result
;;

Это довольно просто: дерево с n> 0 узлами - это дерево с 1 узлом вверху, а затем n-1 узлы внизу разделяются между определеннымичисло слева и определенное число справа.Таким образом, мы делаем цикл для i от 0 до n-1 через все возможные числа значений с левой стороны, и ni-1 будет числом узлов с правой стороны.Мы рекурсивно вызываем all_trees, чтобы получить деревья с узлами i и ni-1, и просто объединяем их.

Обратите внимание, что это очень плохая реализация.В нем есть все, чего должна избегать рекурсивная функция.Посмотрите что-то вроде на этой странице о рекурсивных реализациях последовательности Фибоначчи , чтобы увидеть, как ее улучшить (первое, что нужно сделать, это кэшировать результаты, а не пересчитывать одни и те же вещи много раз).

---

Я согласен с комментариями вопроса, хотя написание проекта было бы шагом 1 в таком проекте, потому что это действительно раздражает необходимость читать такие беспорядочные вещи, как [Node ('x', Node ('x', Empty, Node ('x', Node ('x', Empty, Empty), Empty)), Empty);.Наименование переменных лучше также облегчит людям чтение вашего кода и увеличит вероятность того, что кто-то вам поможет.И вообще, слушая комментарии, когда люди дают вам советы о том, как правильно задавать ваши вопросы, вам будет легче получить ответы как сейчас, так и в ваших будущих вопросах.Например, в своем собственном коде я использовал i в качестве индекса цикла.Это имеет смысл для меня, пока я его кодирую, но когда вы читаете код, возможно, вы бы предпочли прочитать что-то вроде left_side_nodes или что-то подобное, что сделало бы очевидным, что эта переменная должна была делать.То же самое в вашем собственном сценарии: вы можете назвать i что-то вроде subtree или, может быть, что-то еще более явное.На самом деле, правильное именование может помочь вам понять, что не так с вашим кодом.Часто, если вы не можете правильно назвать переменную, вы не понимаете, что она делает (даже локальные переменные).