偏序比较 [英] Partial ordered Comparator

问题描述

如何实施的java.util.Comparator 根据部分顺序关系的命令它的元素？

How to implement java.util.Comparator that orders its elements according to a partial order relation?

例如给予部分顺序关系的在的≺的 C 的 B 的≺的 C 的;顺序的在和 B 的是不确定的。

For example given a partial order relation a ≺ c, b ≺ c; the order of a and b is undefined.

由于比较总共需要订购，为此，部分顺序是随意不确定的，但一致的执行命令的元素。

Since Comparator requires a total ordering, the implementation orders elements for which the partial ordering is undefined arbitrarily but consistent.

请问下面的工作？

interface Item {
    boolean before(Item other);
}

class ItemPartialOrderComperator implements Comparator<Item> {
    @Override
    public int compare(Item o1, Item o2) {
        if(o1.equals(o2)) {  // Comparator returns 0 if and only if o1 and o2 are equal;
            return 0;
        }
        if(o1.before(o2)) {
            return -1;
        }
        if(o2.before(o1)) {
            return +1;
        }
        return o1.hashCode() - o2.hashCode(); // Arbitrary order on hashcode
    }
}

• 这是比较的顺序传递？
  （我担心它是不是）的
• 是比较是需要传递的？
  （在使用时 TreeMap的）的
• 如何正确实现它？
  （如果实现上述方法无效）
  （哈希codeS可以碰撞，为简单起见碰撞的例子忽略碰撞;看达B的回答以<一href="http://stackoverflow.com/questions/28301/impose-a-total-ordering-on-all-instances-of-any-class-in-java">Impose对所有实例*在Java中任何*类的散列codeS故障安全有序。）的
的总体排序
• Is this comparator's ordering transitive?
  (I fear that it is not)
• Are Comparators required to be transitive?
  (when used in a TreeMap)
• How to implement it correctly?
  (if the implementation above doesn't work)
  (Hashcodes can collide, for simplicity collisions the example ignores collisions; see Damien B's answer to Impose a total ordering on all instances of *any* class in Java for a fail-safe ordering on hashcodes.)

推荐答案

问题是，当你拥有无与伦比的元素，你需要回落到的东西比比较散codeS聪明。例如，给定的部分顺序{＆一个所述; B，C＆LT; D}，哈希codeS能满足H（D）＆LT; H（B）＆LT; H（C）＆LT;小时（a）中，这意味着与所述; b ＆LT; C＆LT; ð＆LT; （粗体表示通过散列code扎碎），这将导致问题的一个 TreeMap的。

The problem is that, when you have incomparable elements, you need to fall back to something cleverer than comparing hash codes. For example, given a partial order {a < b, c < d}, the hash codes could satisfy h(d) < h(b) < h(c) < h(a), which means that a < b < c < d < a (bold denotes tie broken by hash code), which will cause problems with a TreeMap.

在一般情况下，有可能是什么让你做，除非拓扑排序事先钥匙，所以关于您感兴趣的部分订单的一些细节将受到欢迎。

In general, there's probably nothing for you to do except topologically sort the keys beforehand, so some details about the partial orders of interest to you would be welcome.

这篇关于偏序比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！