算法排序解决智力谜题/难题

Question

你可能以前见过一些脑筋急转弯的排序问题：

在BrainBashers三项全能比赛的最新一轮中，Keith排名第四。Adrian不是最老的，但比Duncan年长，而Duncan不是第二。年龄次于最小孩子的孩子获得第二名。获得第三名的孩子比获得第一名的孩子年长。Billy比获得第三名的孩子年轻。你能确定谁获得了哪个名次并按年龄顺序排列孩子们吗？[来源] 我正在寻找一种算法方法来解决似乎非常相似的问题。

我有一组对象，想要根据它们之间的规则进行排序。对于给定的规则集，可能会有多个解决方案。在有效的解决方案中，所有规则都得到满足。一组规则也可能没有有效的解决方案。

例如：

对象：A、B、C、D、E和F

规则：

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

一个可能的解决方案：

 F A C E D B

请注意，对象B与其他对象没有关系，因此它出现在序列中的位置无关紧要。

这肯定已经做过了。有人能指点我正确的方向吗？最终我将在Java中执行此排序。

相关问题： Java部分有序集合<E>

- Andy

---

有很多CSP（约束满足问题）求解器可用。http://en.wikipedia.org/wiki/Constraint_satisfaction_problem - MrSmith42

我解决了你在阅读问题时引用的谜题...现在你有足够的答案了...也许我太慢了。或者其他人没有解决这个谜题！ :-) - micha

Answer 1

一个选项是使用规则构建有向图, 然后进行拓扑排序。

注意: 我不知道这是否是最有效的方法，这只是我想到的第一件事。然而，从渐进的角度来看，这是O(N)，因此你不会得到更好的结果！

- Oliver Charlesworth

---

这似乎是正确的方法。但是...我会让这个问题暂时搁置一下，看看会发生什么！ - Andy

Answer 2

这并不高效，但一种简单的暴力方法是：

List<String> names = Arrays.asList("A", "B", "C", "D", "E", "F");
do {
    Collections.shuffle(names);
} while (!(
        names.indexOf("C") < names.indexOf("A") &&
                names.indexOf("C") > names.indexOf("D") &&
                names.indexOf("F") > names.indexOf("C") &&
                names.indexOf("A") < names.indexOf("F") &&
                names.indexOf("E") < names.indexOf("F") &&
                names.indexOf("D") < names.indexOf("E")));
System.out.println("A solution is " + names);

打印输出

A solution is [D, C, A, B, E, F]

- Peter Lawrey

---

这不是类似于O(N.N!)的平均情况吗？ - Oliver Charlesworth

我喜欢它（即使我无法在我的应用程序中使用它）。 - Andy

Answer 3

[编辑，更好的解释] 使用没有前置对象的对象，然后使用没有前置对象但已经使用过的对象，以此类推。

您可以查看对象的所有前置对象，然后查找是否有一个没有前置对象并将其放在第一位置。然后查找没有其他前置对象的对象，除了已经使用过的对象。以此类推...

- pgras