问题标签 [poset]

请帮助我提高以下算法的时间复杂度。

哈斯图（如果您已经知道什么是哈斯图，请跳过此部分，请直接进入下一部分）：

考虑一个偏序集（poset，简称）(A,⊆)，其中A是一个集合，⊆是一个偏序。图的每个节点都是poset的一个元素，如果两个元素 x 和 y 用一条线连接，则 x ⊆ y 或 y ⊆ x 。元素的位置和连接的绘制遵循以下规则：

1. 如果在poset中x⊆y，那么对应于x的点出现在对应于y的点之下。

2. 偏序的传递性在图形上被省略了，也就是说，如果 x ⊆ y 和 y ⊆ z，那么，通过偏序 ⊆ 的传递性，x ⊆ z。在这种情况下，连接 xz 被省略。

3. 类似地，自反性在图形上被省略了。

Poset(S={{1,2,3,5}, {2,3}, {5}, {3}, {1,3}, {1,5}}, ⊆) 的哈斯图表示是如下（只报告边缘）

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

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

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

{2,3}->{3}

{1,3}->{3}

{1,5}->{5}

我最初的想法

我能想到的唯一算法是 O(N^2) 如下：

读取第一个元素是 S 并将其作为第一个元素插入到哈斯图中。当我们阅读下一个元素时，将它们插入已经构建的图表中的正确位置（假设到目前为止构建的图表有 K 个元素，那么在正确的位置插入一个新元素需要 O(K) 时间）。这样 O(N ^ 2) 是显而易见的。

但我在想对poset S的元素进行排序是否有帮助，但无法构建S中完整元素的排序顺序，因为⊆可能不适用于所有元素对（例如，考虑{2,3}和{1,3 }）。

欢迎任何改善最坏情况复杂性的想法！

谢谢。

PS：这不是作业问题！！

我正在寻找一个数据结构的 Java 实现，它包含定义了部分排序的元素集合，并允许以某种拓扑顺序迭代这些元素（任何可能的排序都可以；最好是稳定的随着集合内容的变化进行排序）。

理想情况下，它将实现一个Collection<E>、Set<E>或SortedSet<E>接口并支持该接口上的所有方法。在指定总排序方面，可以用 a 实例化集合，如果要比较的两个元素没有相对于彼此排序，Comparator<E>比较器可能会抛出异常 ( ?)。ClassCastException作为奖励，如果插入的元素会产生排序异常（元素有序图中的循环），它将引发异常。

所以是的，我想要的是拓扑排序，但我想要一个集合对象，它在每次插入/删除时都保持该排序顺序，类似于 SortedSet 如何按排序顺序维护集合。

这样的事情存在吗？在一些开源库中？

参考：

http://en.wikipedia.org/wiki/Partially_ordered_set

http://en.wikipedia.org/wiki/Topological_sorting

更新

在意识到我的要求对性能的影响（以及我无法完全解决的各种其他问题，使用 poset）之后，我最终采用了一种不同的方法来解决我不需要 poset 的问题。依靠比较器来确定元素之间的顺序意味着对于元素插入，我必须针对每个现有元素咨询比较器，每次插入的成本为 O(n)。

如果性能不是很重要（确实如此），并且如果元素的数量限制在合理的范围内（不是），我想我会采用 Willie 建议的方法，尽管可能使用我自己的图形实现和拓扑排序实现以最小化依赖关系。

如何有效地枚举有限集上的所有偏序？

我想检查是否存在具有指定属性的部分订单。为了检查这一点，我将用蛮力枚举小型有限集上所有可能的偏序。

任何人都可以判断是否存在用于在部分有序集中找到大小为 k 的反链的 P 时间算法？（或 DAG）

我在网上找到的所有资源都涉及找到最大的反链。

我有一个部分有序的集合，比如说A = [x1, x2, ...]，这意味着对于集合中的每个xiand xj，（确切地说）四种可能性之一是正确的：xi < xj、xi == xj、xi > xj、 或xi并且xj是无法比较的。

我想找到最大的元素（即那些xi没有元素的元素xj）xi < xj。什么是执行此操作的有效算法（最小化比较次数）？我尝试构建 DAG 并进行拓扑排序，但仅构建图形需要 O(n^2) 比较，这太多了。

我在 Python 中执行此操作，但如果您不知道，我可以阅读其他语言或伪代码。

我有一个使用语句块的程序 EDSL。

尽管语句之间可能存在依赖关系，但这些语句以没有特定顺序添加到块中。

然而，在 EDSL 的编译过程中，我需要确保语句按依赖顺序排序，例如

由于并非所有语句都具有依赖关系，因此没有总顺序（例如E := D，上面是独立的，可以放在任何地方）。没有循环依赖，因此列表排序应该是可能的。

我试图通过使用Data.List.sortBy和定义Ordering将返回EQ意味着语句没有依赖关系来破解解决方案。这适用于一些示例，但不适用于一般情况，例如，订购以下内容没有任何作用：

这是因为默认排序插入排序并且只确保插入的项小于或等于下一项。

我在互联网上搜索了一个 Poset 实现，但没有找到任何适用的：

altfloat:Data.Poset定义Ordering = LT | GT | EQ | NC（NC对于不可比较的）这很好，但提供的sort假设NaN- 类似不可比较的项目，只是把它们扔掉。

logfloat:Data.Number.PartialOrd与上面的类似，除了用途Maybe Ordering，我在包的任何地方都没有看到排序功能。

Math.Combinatorics.Poset我还没有弄清楚如何使用它或它是否适用。

下面是一个最小的例子，它同时具有绑定和非绑定语句。非约束语句的顺序很重要，它们必须保持原始顺序（即排序需要是稳定的 wrt 语句，没有依赖关系）。

我希望在不使用完整的依赖图的情况下有一个简单的解决方案......

我正在尝试计算给定poset的最大反链。我创建了以下方法：

当且仅当两个节点不可比较（即，没有 from atob 或 from bto的路径a）时，它才返回 true。

我定义了一个 LinkedHashMap

它将每个节点 N 映射到其无与伦比的元素Incomp(N)。

例如：假设元素是 {A,B,C,D} 具有以下关系 A>B, A>C, D>C 那么

请注意，不允许重复（即Incomp(C)={B}，但由于 (B,C) 在Incomp(B)我们不需要重复它）。

我被困在这里。我应该只检查Incomp(N)元素之间的不可比性，然后将最大尺寸的密钥作为最大反链吗？换句话说，如何通过这个设置找到最大的反链？

我不能生成所有大小为 k 的子集，因为这将是低效的。

给定一个模块数组，返回一个描述模块之间规范化（最小）排序关系的数组的最佳方法是什么？数组的每个元素都应该是具有父子关系的模块对数组。每对中的子父顺序很重要，但对之间的顺序无关紧要。归一化排序意味着任何可以从传递性派生的东西都应该从数组中排除。

例如，给定[Object, Comparable, Float, Fixnum, Integer]，答案将是：

数组中的五对对应于该哈斯图中的五条边：

提示：如果存在顺序关系，则Module#<=>other返回-1, 0，如果不存在顺序关系。1nil

给定一个部分有序的集合（poset），假设所有线性扩展的可能性相同，估计一个元素在线性扩展中最高的概率的算法是什么？

我计划创建一个表示严格偏序集的类，并且我假设对其接口建模的最自然方法是作为二元关系。这提供了如下功能：

可能的功能如下：

简单的实现是有一个对列表，使得 (a, b) 表示 a < b。但是，它可能不是最优的。例如，test将是线性时间。也许它可以更好地作为列表的哈希映射来完成。

但是，理想情况下，内存中的表示将根据其性质强制applyTransitivity始终“有效”，并且不允许创建导致自反性或对称性的边。换句话说，数据结构的自由度代表了严格偏序集的自由度。有没有已知的方法可以做到这一点？set或者，更现实地说，是否有一种方法可以检查是否是周期性的，并在每次调用and时保持可摊销和迭代的传递性clear，从而降低执行正确性的成本。有工作实施吗？