java - 脑筋急转弯/谜题的算法排序解决方案

Question

您之前可能看过点脑筋急转弯:

During the latest round of the BrainBashers triathlon, Keith wasfourth. Adrian is not the oldest, but is older than Duncan, who wasnot second. The child who was next in age to the youngest, finishedsecond. The child who finished in third place is older than the childwho finished first. Billy is younger than the child who finished inthird place. Can you determine who finished where and place thechildren in order of age? [Source]

我正在寻找一种算法方法来解决看起来非常相似的问题。

我有一组对象，我想根据对象彼此相关的规则对其进行排序。对于一组给定的规则，可能有多个解决方案。在一个有效的解决方案中，所有的规则都得到满足。一组规则也可能没有有效的解决方案。

示例:

对象:A, B, C, D, E, and F

规则:

• C > A
• C < D
• F < C
• A > F
• E > F
• D > E

一种可能的解决方案:

 F A C E D B

请注意，对象 B 与任何其他对象都不相关，因此它在序列中出现的位置并不重要。

肯定以前有人这样做过。谁能指出我正确的方向？我最终将使用 Java 执行这种排序。

相关问题: Java partially ordered Collection<E>

Answer 1

一个选择是使用规则来构建一个 directed graph , 然后执行 topological sort .

注意:我不知道这是否是最有效的方法，这只是我想到的第一件事。但是，这是 O(N)，因此从渐近的角度来看，您不会做得更好!