基于有向图树建立列表的年表
Establishing chronology of a list based on a directed graph tree
因此，在我一直从事的个人项目中，我遇到了以下问题，由于我的数学技能不是很好，我一直在努力想出一个解决方案。
假设您有以下数字树 a b c d e f g h:
a
/ \
b c
/ | |
g d f
| |
h e
树下的每一步都意味着下一个数字比前一个数字大。所以 a < b，d < e，a < c。但是，无法确定是 b > c 还是 c < b - 我们只能说这两个数字都比 a 大。
假设我们有一个有序的数字列表，例如 [a, b, c, d, e]。我们如何编写一个算法来检查列表中数字的顺序（假设 L[i] < L[i+1]）实际上相对于我们根据这棵树获得的信息是正确的？
我。 E，[a, c, b, d, e] 和 [a, b, d, c, e] 都是正确的，但是 [c, a, b, d, e] 不正确（因为我们知道 c > a 但与其他数字的结构无关。
为了算法的缘故，假设我们对树的访问是一个函数 provably_greater(X, Y) 如果树知道一个数字更高则 returns 为真另一个号码。 IE。 provably_greater(a, d) = True，但 provably_greater(d, f) = False。自然地，如果一个数字被证明不是更大的，那么它也是 returns false。
这不是一道作业题，我已经将问题抽象了很多以使其更清楚，但是解决这个问题对于我正在尝试的事情来说非常关键做。我已经多次尝试自己破解它，但我想出的一切最终都不足以解决我后来发现的一些边缘情况。
提前致谢。
你的说法"everything that I come up with ends up being insufficient for some edge case I find out about later"让人觉得你根本没有解决办法。这是 一个 brute-force 算法 应该适用于所有情况。我可以想到几种可能的方法来提高速度，但这是一个开始。
首先，建立一个数据结构，允许基于树快速评估provably_greater(X, Y)。该结构可以是集合或 hash-table，这将占用大量内存但允许快速访问。对于树的每一片叶子，走一条通往根的路径。在每个节点处，查看所有后代节点并向集合中添加一个有序对，以显示这两个节点的 less-than 关系。在您的示例树中，如果您从节点 h 开始，则向上移动到节点 g 并将 (g,h) 添加到集合中，然后向上移动到节点 b 并添加对(b,h) 和 (b,g) 到集合，然后向上移动到节点 a 并将对 (a,h)、(a,g) 和 (a,b) 添加到集合.对叶节点 e 和 f 执行相同的操作。由于叶节点 h 和 e，(a,b) 对将被添加到集合中两次，但集合结构可以轻松处理此问题。
函数 provably_greater(X, Y) 现在变得简单快捷：如果 (Y,X) 对在集合中，结果为 True，否则为 False。
您现在查看列表中的所有数字对——对于列表 [a,b,c,d,e]，您将查看 (a,b)、(a,c)、(b,c) 对，等等。如果 provably_greater(X, Y) 对于这些对中的任何一个为真，则列表是乱序的。否则，列表是有序的。
这应该很容易用像 Python 这样的语言来实现。如果您想要一些 Python 3 代码，请告诉我。
我将忽略您的 provably_greater 函数并假定可以访问树，以便我可以提供有效的算法。
首先，执行树的欧拉巡回，记住每个节点的开始和结束索引。如果您使用同一棵树来检查很多列表，则只需执行一次。参见 https://www.geeksforgeeks.org/euler-tour-tree/
创建一个初始为空的索引二叉搜索树
遍历列表。对于每个节点，检查树是否包含其开始和结束 Euler 游览索引之间的任何索引。如果是这样，那么列表就乱序了。如果没有，则将其起始索引插入树中。这将防止任何可证明的较小节点出现在列表的后面。
就是这样 -- 总共 O(N log N)，对于每个列表。
Java中的TreeSet或C++中的std::set可用于二叉搜索树。
因此，在我一直从事的个人项目中，我遇到了以下问题，由于我的数学技能不是很好，我一直在努力想出一个解决方案。
假设您有以下数字树 a b c d e f g h:
a
/ \
b c
/ | |
g d f
| |
h e
树下的每一步都意味着下一个数字比前一个数字大。所以 a < b，d < e，a < c。但是，无法确定是 b > c 还是 c < b - 我们只能说这两个数字都比 a 大。
假设我们有一个有序的数字列表，例如 [a, b, c, d, e]。我们如何编写一个算法来检查列表中数字的顺序（假设 L[i] < L[i+1]）实际上相对于我们根据这棵树获得的信息是正确的？
我。 E，[a, c, b, d, e] 和 [a, b, d, c, e] 都是正确的，但是 [c, a, b, d, e] 不正确（因为我们知道 c > a 但与其他数字的结构无关。
为了算法的缘故，假设我们对树的访问是一个函数 provably_greater(X, Y) 如果树知道一个数字更高则 returns 为真另一个号码。 IE。 provably_greater(a, d) = True，但 provably_greater(d, f) = False。自然地，如果一个数字被证明不是更大的，那么它也是 returns false。
这不是一道作业题，我已经将问题抽象了很多以使其更清楚，但是解决这个问题对于我正在尝试的事情来说非常关键做。我已经多次尝试自己破解它，但我想出的一切最终都不足以解决我后来发现的一些边缘情况。
提前致谢。
你的说法"everything that I come up with ends up being insufficient for some edge case I find out about later"让人觉得你根本没有解决办法。这是 一个 brute-force 算法 应该适用于所有情况。我可以想到几种可能的方法来提高速度，但这是一个开始。
首先，建立一个数据结构，允许基于树快速评估provably_greater(X, Y)。该结构可以是集合或 hash-table，这将占用大量内存但允许快速访问。对于树的每一片叶子，走一条通往根的路径。在每个节点处，查看所有后代节点并向集合中添加一个有序对，以显示这两个节点的 less-than 关系。在您的示例树中，如果您从节点 h 开始，则向上移动到节点 g 并将 (g,h) 添加到集合中，然后向上移动到节点 b 并添加对(b,h) 和 (b,g) 到集合，然后向上移动到节点 a 并将对 (a,h)、(a,g) 和 (a,b) 添加到集合.对叶节点 e 和 f 执行相同的操作。由于叶节点 h 和 e，(a,b) 对将被添加到集合中两次，但集合结构可以轻松处理此问题。
函数 provably_greater(X, Y) 现在变得简单快捷：如果 (Y,X) 对在集合中，结果为 True，否则为 False。
您现在查看列表中的所有数字对——对于列表 [a,b,c,d,e]，您将查看 (a,b)、(a,c)、(b,c) 对，等等。如果 provably_greater(X, Y) 对于这些对中的任何一个为真，则列表是乱序的。否则，列表是有序的。
这应该很容易用像 Python 这样的语言来实现。如果您想要一些 Python 3 代码，请告诉我。
我将忽略您的 provably_greater 函数并假定可以访问树，以便我可以提供有效的算法。
首先，执行树的欧拉巡回，记住每个节点的开始和结束索引。如果您使用同一棵树来检查很多列表，则只需执行一次。参见 https://www.geeksforgeeks.org/euler-tour-tree/
创建一个初始为空的索引二叉搜索树
遍历列表。对于每个节点，检查树是否包含其开始和结束 Euler 游览索引之间的任何索引。如果是这样，那么列表就乱序了。如果没有，则将其起始索引插入树中。这将防止任何可证明的较小节点出现在列表的后面。
就是这样 -- 总共 O(N log N)，对于每个列表。
Java中的TreeSet或C++中的std::set可用于二叉搜索树。