问题标签 [partial-ordering]

可能最好用一个小例子来说明。
鉴于关系

正确的输出将是

换句话说，任何给定关系成立的排序都是有效的。

我对最容易实现的解决方案最感兴趣，但速度和时间上最好的 O(n) 也很有趣。

在阅读另一个问题时，我遇到了部分排序问题，我将其缩减为以下测试用例

对于这两个函数模板，进入重载决议的特化的函数类型是void(int, void*). 但是偏序（根据 Comeau 和 GCC）现在说第二个模板更专业。但为什么？

让我通过部分排序并显示我有问题的地方。可能Q是一种独特的组合类型，用于根据 确定偏序14.5.5.2。

• 转换后的参数列表T1（Q 插入）(Q, typename Const<Q>::type*)：。参数的类型是AT=(Q, void*)
• T2(Q 插入): BT=的转换参数列表(Q, void*)，这也是参数的类型。
• 未转换的参数列表T1：(T, typename Const<T>::type*)
• 未转换的参数列表T2：(T, void*)

由于 C++03 没有明确说明这一点，我确实使用了我在几个缺陷报告中读到的意图。上面转换的参数列表T1（AT由我调用）用作14.8.2.1 “从函数调用中推导出模板参数”的参数列表。

14.8.2.1不再需要转换ATorBT本身（例如，删除引用声明符等），并直接转到14.8.2.4，对于每个A/P对独立地进行类型推导：

• AT反对T2：。是这里唯一的模板参数，它会发现必须是. 类型推导对于against轻而易举地成功。{ (Q, T), (void*, void*) }TTQATT2

• BT反对T1：。它会发现is , too here。是一个未推断的上下文，因此它不会用于推断任何内容。{ (Q, T), (void*, typename Const<T>::type*) }TQtypename Const<T>::type*

这是我的第一个问题：现在这将使用Tdeduced 的值作为第一个参数吗？如果答案是否定的，那么第一个模板更专业。这不可能，因为 GCC 和 Comeau 都说第二个模板更专业，我不认为他们错了。所以我们假设“是”，然后void*插入T. 段落 ( 14.8.2.4) 说“对每一对独立进行推导，然后将结果组合起来”以及“但是，在某些情况下，该值不参与类型推导，而是使用推导出来的模板参数的值在别处或明确指定。” 这听起来也像“是”。

因此，对于每个 A / P 对，演绎也成功。现在，每个模板至少和另一个模板一样专业化，因为演绎也不依赖于任何隐式转换并且在两个方向上都成功了。因此，调用应该是模棱两可的。

所以我的第二个问题：现在，为什么实现说第二个模板更专业？我忽略了哪一点？

编辑：我测试了显式特化和实例化，并且在最近的 GCC 版本 ( 4.4) 中都告诉我对特化的引用是模棱两可的，而旧版本的 GCC ( 4.1) 不会出现这种模棱两可的错误。这表明最近的 GCC 版本对函数模板的偏序不一致。

我有一个具有偏序关系的项目列表，即。e，列表可以被认为是一个偏序集。我想以与此问题相同的方式对该列表进行排序。正如那里正确回答的那样，这称为拓扑排序。

有一个相当简单的已知算法来解决这个问题。我想要一个类似于 LINQ 的实现。

我已经尝试过使用OrderBy扩展方法，但我很确定它无法进行拓扑排序。问题是IComparer<TKey>接口不能表示部分顺序。发生这种情况是因为该Compare方法基本上可以返回 3 种值：zero、negative和positive，分别表示 are-equal、is-less-than和is-greater-then。只有有办法返回are-unrelated ，才有可能找到可行的解决方案。

从我的偏见的角度来看，我正在寻找的答案可能由一个IPartialOrderComparer<T>接口和一个扩展方法组成，如下所示：

这将如何实施？IPartialOrderComparer<T>界面会是什么样子？你会推荐一种不同的方法吗？我很想看到它。也许有更好的方式来表示偏序，我不知道。

语境：

我有一个很小（目前不到 100 个）但不断增长的正则表达式集合，我想优化确定给定文本字符串的过程，以确定我的集合中哪些 RE 与文本字符串匹配。

一些 RE 具有排序关系——例如，如果我知道字符串 $t 匹配 /windows/i，那么我也知道 $t 匹配 /windows.*2000/i。因此，在针对我的集合中的 RE 测试 $t 时，如果我已经针对 /windows.*2000/i 测试了 $t 并找到了匹配项（尽管 /windows.*2000/i 确实如此，那么我可以跳过测试 /windows/i不匹配那么我当然不能跳过对 /windows/i 的测试）。

请注意，我的集合中没有一个 RE 是完全等价的（对于任何一对 RE，至少有一个文本字符串与一个匹配而另一个不匹配）。

战略：

我想为我的集合中的每个 RE 构建一个有向图 G，并为每对具有排序关系的 RE 构建一个有向边（A -> B 表示“与 A 匹配意味着与 B 匹配”），并找到一个图的节点的“最小跨越集”（最小节点集 S 使得 G 中的每个节点都位于源自 S 的有向路径上）。

最简单的部分：

有许多免费可用的算法可用于处理有向无环图。因此，一旦为我的 RE 集合构建了图 G（不同的应该保证 G 是非循环的），我预计找到合适的算法来为 G 找到最小跨度集不会有太大困难。

我需要帮助的地方：

我想找到一种有效的方法来查找我的集合中的 RE 之间的所有排序关系——也许还可以确保集合中没有两个 RE 是等效的（我需要一种方法来自动验证这一点，因为新的 RE 是添加）。

因此，我的（基本上是随机的）网络搜索至少出现了一个合理的说法，即确实存在一种合理的方法来计算两个 RE 之间存在什么（如果有的话）排序关系，但还没有出现对完整算法的任何描述。

有谁知道现有的实现（用于比较 RE），它相当高效、免费提供，并且（理想情况下）用一种流行的脚本语言或 C/C++ 实现？

我有一个依赖项列表（或者更好的是没有循环的 DAG）：

输入（例如）：

我正在寻找的是：“项目的最佳*并行顺序是什么？”

*最好的意思是：最大并发级别

结果（例如）：

最好的方法似乎是基于依赖关系获取订单的伪代码，但我想我错过了一个基本算法。

下面的一段代码

在 Python 2 中运行良好，但在 Python 3 中出现错误：

它仅适用于==和!=。

这是我的问题：我有一个（非空但可能不是不同的）集合 s_i 的序列 S，并且对于每个 s_i，需要知道 S（i ≠ j）中有多少个集合 s_j 是 s_i 的子集。

我还需要增量性能：一旦我有了所有的计数，我可以用 s_i 的某个子集替换一组 s_i 并逐步更新计数。

使用纯函数式代码执行所有这些将是一个巨大的优势（我在 Scala 中编写代码）。

由于集合包含是部分排序，我认为解决我的问题的最佳方法是构建一个 DAG，它表示集合的 Hasse 图，边表示包含，并将一个整数值连接到每个节点，表示节点下面的子 dag 加 1。但是，我已经被困了好几天，试图开发从偏序构建 Hasse 图的算法（我们不谈论增量！），即使我认为它会是一些标准的本科材料。

这是我的数据结构：

我的 DAG 由根列表和一些部分排序定义：

我被困在这里了。最后我想为 DAG 添加一个新值 v 是：

1. 在 DAG 中找到 v 的所有“根子集”rs_i，即 v 的子集，使得 rs_i 的任何超集都不是 v 的子集。这可以通过在图上执行搜索（BFS 或 DFS）很容易地完成（collect函数，可能不是最佳的甚至是有缺陷的）。
2. 构建新节点 n_v，其子节点是先前找到的 rs_i。
3. 现在，让我们找出应该附加 n_v 的位置：对于给定的根列表，找出 v 的超集。如果没有找到，将 n_v 添加到根并从根中删除 n_v 的子集。否则，对超集的孩子递归执行第 3 步。

我还没有完全实现这个算法，但对于我看似简单的问题来说，它似乎是不必要的迂回和非最优的。是否有一些更简单的算法可用（谷歌对此一无所知）？

It seems that scala.math.PartialOrdering.lteq must always be defined as (or at least, give the same result as):

Is there some reason this implementation isn't given in the scala.math.PartialOrdering trait?

为什么这是模棱两可的？

我知道这是部分排序上下文。而我的，可能是错误的想法是：#2 中的任何 T& 都可以放入 #1，但 #1 中的任何 T 都不是合法的 #2。所以部分排序应该有效。

在我的代码中，我使用了一个表示有向无环图的类。我自己写了代码，并不难。但后来我意识到我的应用程序有更多的要求：图必须是传递减少的，即偏序的唯一表示。每次用户在图形的可视 GUI 表示上进行拖放或剪切/复制/粘贴时，都必须对其进行验证并适应此要求。现在事情变得更加复杂了。所以我确实计划了如何安全地执行所有图形操作等，但在我真正深入研究代码之前，我想知道：

是否有用于部分订单的已知 C/C++ 接口？（最好是 C++）

我发现了很多图形库，但我已经有了简单的非循环有向图代码。我找不到任何专门处理传递减少图的东西（我不需要邻接矩阵，数据来自用户，所以在这里效率低下......这是用户数据的小图，而不是用于数学用途）

我正在寻找一个接口，它可以自动检测不必要的连接并删除它们，进行测试以查看节点复制/移动操作是否按偏序有效，即保留偏序的属性等。