查找部分有序集的最大元素的高效算法 [英] Efficient algorithm to find the maximal elements of a partially ordered set

问题描述

我有一个部分排序的集合，例如 A = [x1，x2，...] ，这意味着每个 xi 和 xj 在集合中，（完全）四种可能性之一是正确的： xi< xj ， xi == xj ， xi> xj 或 xi 和 xj 是无法比拟的。

I have a partially ordered set, say A = [x1, x2, ...], meaning that for each xi and xj in the set, (exactly) one of four possibilities is true: xi < xj, xi == xj, xi > xj, or xi and xj are incomparable.

我想找到最大元素（即那些元素 xi 中没有元素 xj 和 xi< xj ）。有什么有效的算法可以做到这一点（尽量减少比较次数）？我尝试构建DAG并进行拓扑排序，但是仅构建图就需要O（n ^ 2）比较，这太多了。

I want to find the maximal elements (i.e., those elements xi for which there are no elements xj with xi < xj). What is an efficient algorithm to do this (minimize the number of comparisons)? I tried building a DAG and doing a topological sort, but just building the graph requires O(n^2) comparisons, which is too many.

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

I'm doing this in Python, but if you don't know it I can read other languages, or pseudocode.

推荐答案

无论您做什么，似乎最坏的情况是O（n ^ 2）。例如，如果没有可比较的元素，则需要将每个元素与其他所有元素进行比较，以确定它们都是最大的。

It seems the worst case is O(n^2) no matter what you do. For example, if no elements are comparable, then you need to compare every element to every other element in order to determine that they are all maximal.

如果允许O （n ^ 2），由于排序是可传递的，因此您可以遍历该集合，并保留到目前为止最大的所有元素的列表；每个新元素都剔除任何<如果它不< ;，则将其添加到最大列表中。任何最大元素。

And if you allow O(n^2), since the ordering is transitive, you can just make one pass through the set, keeping a list of all elements that are maximal so far; each new element knocks out any maximal elements that are < it and gets added to the maximal list if it is not < any maximal element.

这篇关于查找部分有序集的最大元素的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！