生成所有可能的树 [英] Generate All Possible Trees

问题描述

给定以下数据类型定义：

 数据FormTree =空|节点FormTree FormTree派生Show 
  

我想编写一个函数来生成一个包含所有可能的树的无限列表在...之后节点的数量。

下面的代码几乎可以满足我的需求，但它只是通过每次插入额外的节点来降低右侧的树，但我需要它来替代。

  allPossibleTrees :: [FormTree] 
 allPossibleTrees =空：[Node xy | x<  - 递归，y<  - 递归] 
其中recursive = allPossibleTrees 
  

执行

  take 5 allPossibleTrees 
  

给出：

  [空，节点为空，节点为空（节点为空），节点为空节点为空（节点为空）），节点为空（节点为空（节点为空（节点为空））]] 
  

但它应该是这样的：

  [空，节点为空，节点（节点为空）空，节点为空（节点为空），节点（节点为空）（节点为空）] 
  

解决方案

这里有一个很好的技巧，让人想起标准的斐波那契数字技巧。我们将建立一个懒惰的列表;列表中的每个成员将是具有给定数量节点的所有树的列表。只有一棵没有节点的树， Empty ，这将作为我们的基本情况。为了构建所有具有 n 节点的树，我们假设我们已经知道如何使用 0 ， 1 ， 2 ，...， n-1 节点。然后，我们只是非确定性地选择一对结合到 n-1 并卡住 Node 的配对

在代码中：

  import Control.Monad 
 import Data.List 
 
 sizes :: [[FormTree]] 
 sizes = [空]：（map go。drop 1。inits）size其中
变小= 
（ls，rs）< -  zip小（反转小）
 liftM2节点ls rs 
  

然后我们可以简单地定义 allPossibleTrees = concat sizes ，如果需要的话。前几项：

  * Main> mapM_ print（取4个大小）
 [空] 
 [节点空]空白] 
 [节点空（节点空空）]，节点空节点空节点空节点空节点空节点空节点空节点空节点空节点空节点空节点空节点空节点空节点空（Node Empty Empty）空）空] 
  

我们可以快速进行完整性检查：

  * Main> 10（地图长度）
 [1,1,2,5,14,42,132,429,1430,4862] 
  

...这确实是前十个加泰罗尼亚语数字，所以我们可能说得对！

Given the following data type definition:

data FormTree = Empty | Node FormTree FormTree deriving Show

I want to write a function which generates an infinite list containing all possible trees sorted after length e.g. the amount of nodes.

The following code almost does what I need but it only descends the tree on the right side by inserting additional nodes every time but I need it to alternate between both sides.

allPossibleTrees :: [FormTree]
allPossibleTrees = Empty : [Node x y | x <- recursive, y <- recursive]
    where recursive = allPossibleTrees

Executing

take 5 allPossibleTrees

gives:

[Empty,Node Empty Empty,Node Empty (Node Empty Empty),Node Empty (Node Empty (Nodes Empty Empty)),Node Empty (Node Empty (Node Empty (Node Empty Empty)))]

but it should be something like:

[Empty,Node Empty Empty,Node (Node Empty Empty) Empty,Node Empty (Node Empty Empty),Node (Node Empty Empty) (Node Empty Empty)]

解决方案

Here's a nice trick, reminiscent of the standard Fibonacci numbers trick. We'll build a lazy list; each member of the list will be a list of all trees with a given number of nodes. There's just one tree with no nodes, Empty, and that will serve as our base case. To build all the trees with n nodes, we'll assume we already know how to build trees with 0, 1, 2, ..., n-1 nodes. Then we'll just non-deterministically choose a pairing of those that sums to n-1 and stuck a Node on top.

In code:

import Control.Monad
import Data.List

sizes :: [[FormTree]]
sizes = [Empty] : (map go . drop 1 . inits) sizes where
    go smaller = do
      (ls, rs) <- zip smaller (reverse smaller)
      liftM2 Node ls rs

Then we can simply define allPossibleTrees = concat sizes if that's wanted. The first few entries:

*Main> mapM_ print (take 4 sizes)
[Empty]
[Node Empty Empty]
[Node Empty (Node Empty Empty),Node (Node Empty Empty) Empty]
[Node Empty (Node Empty (Node Empty Empty)),Node Empty (Node (Node Empty Empty) Empty),Node (Node Empty Empty) (Node Empty Empty),Node (Node Empty (Node Empty Empty)) Empty,Node (Node (Node Empty Empty) Empty) Empty]

We can do a quick sanity check:

*Main> take 10 (map length sizes)
[1,1,2,5,14,42,132,429,1430,4862]

...which is indeed the first ten Catalan numbers, so we probably got it right!

这篇关于生成所有可能的树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！