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

Question

你知道是否有可能以某种方式生成一个具有特定分支因子的随机树图？我不希望它是一棵k-ary树.

如果我可以定义分支因子和最大深度,那也是很好的.我想随机生成一堆树枝,它们的分枝因子和深度都不同.

随机整数输入的TreePlot返回几乎我想要的东西:

TreePlot[RandomInteger[#] -> # + 1 & /@ Range[0, 100]]

但我无法弄清楚如何获得具有特定分支因子的树.

谢谢!

Answer 1

我想我有点晚了，但我喜欢这个问题。而不是以形式创建树

{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来定义（子）树可以具有的最大深度。

1. [选择分支]定义一个分支函数f，可以像这样调用f[]并返回随机数量的子级。如果你想要一棵有 2 或 4 个子节点的树，你可以使用例如f[] := RandomChoice[{2, 4}]。将为树中每个创建的节点调用此函数。

2. [选择树深度]d选择树的最大深度。此时，我不确定您希望将什么随机性纳入树的生成中。我在这里所做的是，当创建一个新节点时，它下面的树的深度是在其父节点的深度减一和零之间随机选择的。

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

4. [创建节点]增加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}]]