10

考虑一个二叉树：

  1. n是一个节点，如果n是一个整数
  2. (+ a b ) 是一个节点，如果a和b是节点。

我们有以下三个操作：

  1. (+ a b ) -> (+ b a )
  2. (+ (+ a b ) c ) -> (+ a (+ b c ))
  3. (+ a (+ b c )) -> (+ (+ a b ) c ) -- (2. 反向)

我需要一种算法来使用这些操作给出给定树的所有可能排列。任何操作都可以应用于任何子树。对于排列，我的意思是任何具有完全相同的叶子的树。这可能不是很困难，但我似乎无法弄清楚。

[编辑]叶子也可以是名称（即变量），因此不能选择将它们的属性作为整数。树确实代表了总和。

[Edit2] 本练习的重点是通过查找A和-A形式的项来减少总和，将树调成子树 (+ A -A ) 以消除它们。上面这三个操作是我系统中的公理，需要一直用到，否则无法证明归约树与原树相等。由于我使用的是十二逻辑编程语言，如果我能找出一个算法来完成我最初提出的要求，其余的就很容易了，但当然欢迎替代解决方案。

4

6 回答 6

2

似乎最直接的解决方案是对树进行深度优先遍历，将所有节点收集到一个列表中，生成列表的所有排列，将每个排列转储到二叉树中。

因此，给定列表 (+ a (+ bc) )，我们有节点 [a; 乙; c]，具有以下排列：

[a; b; c]
[a; c; b]
[b; a; c]
[b; c; a]
[c; a; b]
[c; b; a]

列表中的第一项是您的头部，以下两项是子节点，接下来的四项是子子节点，依此类推。

如果您需要生成所有可能的树的列表，而不仅仅是平衡的树，则此操作的复杂性会显着增加。在这种情况下，您需要像这样对它们进行分组：

[a; b; c; d]
[(a; b); c; d]
[(a; b; c); d]
[a; (b; c); d]
[a; (b; c; d)]
[a; b; (c; d)]
[a; b; d; c]
// first permutation
[(a; b); d; c]
[(a; b; d); c]
...

其中每个 n 元组是一组节点。对于不止几个节点，宇宙将在你的算法完成之前经历热寂。

于 2009-03-16T18:51:34.253 回答
1

这个问题的解决方案无疑将包括加泰罗尼亚数字。有C n -1个可能的二叉树，有n 个叶子，并且有n！叶子的可能排序，所以有n！* C n -1种可能的树。不过，枚举它们有点棘手。

于 2009-03-16T18:47:26.587 回答
1

这些操作类似于具有以下属性的加法：闭包、结合性、交换性。对于一个匹配节点，每个节点的叶子集合都是相同的，并且可以以递归方式应用。计算给定节点 x 的排列（在 Haskell 和 F# 的一些奇怪组合中）

let count x = match x with
  | LeafNode -> 1
  | TreeNode (a,b) -> 2 * count a * count b
于 2009-03-16T18:47:57.710 回答
1

您具有关联性和交换性，因此您可以自由移动元素。解决此问题的实用方法如下所示：

  • 把树梳到一边，你会得到一个列表。

  • 对列表进行排序，使应该取消的元素彼此相邻。

  • 将元素移动到子树中并取消。

要获得所需的证明，您必须为这些操作构建小证明，然后将其组合起来。

或者，您可以查找 AC 匹配。

按照您的建议尝试所有排列只会让您获得巨大的组合爆炸。

于 2009-03-16T22:08:38.990 回答
1

正如所指出的，如果你真的有交换性和结合性公理，你最好只收集和处理它们作为一个集合或一个列表。

如果这不令人满意，接下来要观察实际上您似乎不需要所有排列，但是您想重写表达式以简化它们。这可以比产生所有排列更有效！

但是，重复:)，如果您只有交换性和关联性，请处理一组中的术语。

于 2009-03-17T00:19:45.790 回答
0

我发现了减少树木的根本问题的解决方案：

  1. 从树中找到一对叶子 A 和 -A。
  2. a) 如果 A 和 -A 在同一个孩子中，则递归。
  3. b) 'Bubble' A 和 -A 到它们各自孩子的顶部。有八种可能的结果情况，但它们看起来都像这样 (+ (x A) (-A y))。从那个到 (+ (+ xy) (+ A -A)) 很容易。

正如建议的那样，另一种方法是首先将树转换为列表：(+ A (+ B (+ ...)) X)，然后找到匹配的 A 和 -A 对并将它们置于顶部。我怀疑这可能会产生比上述算法更长的证明（这是不可取的），尽管我没有尝试过。

尽管如此，我发现最初的问题很吸引人，我想尝试基于该算法的算法与上述问题的比较。

于 2009-03-17T12:34:33.107 回答