Mathematica中具有特定分支因子的随机树

1 回答

• 4

  我想我有点晚了，但我喜欢这个问题 . 而不是在表单中创建树

  {0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}
  

  我将使用以下形式的嵌套调用，其中每个参数都是一个子节点，它代表另一个节点

  0[1[2, 3, 4], 5]
  

  两种形式都是等同的，可以相互转化 .

  Row[{
    TreeForm[0[1[2, 3, 4], 5]],
    TreePlot[{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}]
    }]
  

  

  以下是算法的工作原理：作为参数，我们需要一个函数 f ，它给出一个随机数的子节点，并在创建节点时调用 . 另外，我们有一个深度 d ，它定义了（子）树可以拥有的最大深度 .

  • [Choose branching] 定义分支函数 f ，可以像 f[] 一样调用并返回随机数的子项 . 如果你想要一个有2个或4个孩子的树，你可以使用例如 f[] := RandomChoice[{2, 4}] . 将为树中的每个已创建节点调用此函数 .

  • [Choose tree-depth] 选择树的最大深度 d . 在这一点上，我不确定你想要将随机性整合到树的生成中 . 我在这里做的是，当创建一个新节点时，它下面的树的深度是在它的父深度减去1和零之间随机选择的 .

  • [Create ID Counter] 创建唯一的计数器变量 count 并将其设置为零 . 这将使我们增加节点ID . 创建新节点时，它会增加1 .

  • [Create a node] 增加 count 并将其用作节点ID . 如果当前深度 d 为零，则返回具有ID计数的叶子，否则调用 f 以确定节点应该获得多少个子节点 . 对于每个新孩子，随机选择其子树的深度，可以是 0,...,d-1 ，并为每个新孩子调用4.返回所有递归调用后，将构建树 .

  幸运的是，在Mathematica代码中，这个过程并不那么冗长，只包含几行 . 我希望你能在代码中找到我上面描述的内容

  With[{counter = Unique[]},
   generateTree[f_, d_] := (counter = 0; builder[f, d]);
   builder[f_, d_] := Block[
     {nodeID = counter++, childs = builder[f, #] & /@ RandomInteger[d - 1, f[]]},
     nodeID @@ childs
   ];
   builder[f_, 0] := (counter++);
  ]
  

  现在，您可以创建如下的随机树

  branching[] := RandomChoice[{2, 4}];
  t = generateTree[branching, 6];
  TreeForm[t]
  

  

  或者，如果您愿意，可以使用下一个函数将树转换为 TreePlot 接受的内容

  transformTree[tree_] := Module[{transform},
    transform[(n_Integer)[childs__]] := (Sow[
       n -> # & /@ ({childs} /. h_Integer[__] :> h)]; 
      transform /@ {childs});
    Flatten@Last@Reap[transform[tree]
  ]
  

  并用它来创建许多随机树

  trees = Table[generateTree[branching, depth], {depth, 3, 7}, {5}];
  GraphicsGrid[Map[TreePlot[transformTree[#]] &, trees, {2}]]
  

  

  回复于 2024-04-20T20:21:55+08:00