3

您之前可能已经看过订购脑筋急转弯：

在最近一轮的 BrainBashers 铁人三项赛中，Keith 排名第四。阿德里安不是最年长的，但比邓肯还大，邓肯排在第二位。年龄仅次于最小的孩子获得第二名。第三名的孩子比第一名的孩子大。比利比获得第三名的孩子小。你能确定谁在哪里完成并按年龄排列孩子吗？[资源]

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

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

例子：

对象：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>

4

3 回答 3

6

一种选择是使用规则构建有向图，然后执行拓扑排序。

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

于 2013-01-03T16:56:16.213 回答
3

它效率不高，但一种简单的蛮力方法是

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]
于 2013-01-03T16:57:59.740 回答
1

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

您可以查看一个对象的所有前辈，然后查看是否找到没有前辈的对象并将其放置在第一个位置。然后，您寻找除了已经使用过的对象之外没有其他前任的对象。等等...

于 2013-01-03T16:59:19.473 回答