如何排序不完整？ [英] How to sort with incomplete ordering?

问题描述

我有一个要排序的元素列表和一个比较函数 cmp（x，y），该函数确定是否 x 应该出现在 y 之前或 y 之后。问题是某些元素没有定义的顺序。 cmp 函数返回 不在乎。

I have a list of elements to sort and a comparison function cmp(x,y) which decides if x should appear before y or after y. The catch is that some elements do not have a defined order. The cmp function returns "don't care".

示例：输入： [A，B，C，D] 和 C> D ， B> D 。输出：许多正确答案，例如 [D，C，B，A] 或 [A，D，B，C] 。我需要的是所有可能输出的一个输出。.

Example: Input: [A,B,C,D], and C > D, B > D. Output: many correct answers, e.g. [D,C,B,A] or [A,D,B,C]. All I need is one output from all possible outputs..

我无法将Python的 sort 用于这和我的解决方法是老式的气泡排序，从空列表开始，然后一次在正确的位置插入一个元素，以使列表始终保持排序。

I was not able to use the Python's sort for this and my solution is the old-fashioned bubble-sort to start with an empty list and insert one element at a time to the right place to keep the list sorted all the time.

是否可以将内置的 sort / sorted 函数用于这个目的？

Is it possible to use the built-in sort/sorted function for this purpose? What would be the key?

推荐答案

这是不可能的。相反，您需要实现拓扑排序。

It's not possible to use the built-in sort for this. Instead, you need to implement a Topological Sort.

这篇关于如何排序不完整？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！