部分有序的比较器

Question

如何实现java.util.Comparator根据偏序关系对其元素进行排序？

例如,给定的部分顺序关系一个 ≺ Ç,b ≺ Ç ; a和b的顺序是不确定的.

由于Comparator需要总排序,因此实现命令部分排序未定义但是一致的元素.

以下工作会怎样？

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
    }
}

• 这个比较器的订购是否具有传递性？
  (我担心不是)
• 是否Comparators需要传递？
  (用于a时TreeMap)
• 如何正确实现？
  (如果上面的实现不起作用)
  (Hashcodes可能会发生碰撞,为了简单碰撞,该示例忽略了冲突;请参阅Damien B 对Java中所有*any*类实例的总排序的回答,以便对哈希码进行故障安全排序.)

Answer 1

问题是,当你拥有无法比较的元素时,你需要回到比比较哈希码更聪明的东西.例如,给定部分顺序{a <b,c <d},哈希码可以满足h(d)<h(b)<h(c)<h(a),这意味着a <b < c <d < a(粗体表示由哈希码破坏的绑定),这将导致a的问题TreeMap.

一般来说,除了事先对键进行拓扑排序之外,您可能无需做任何事情,因此欢迎您关注部分顺序的一些细节.

Answer 2

它似乎更像是一个答案,而不是一个评论所以我会发布它

该文件说:

从比较合同中可以看出,商是S上的等价关系,强加的排序是S的总订单.

所以不,比较器需要总排序.如果您通过部分订购实现此操作,则违反了接口合同.

即使它可能在某些情况下有效,也不应试图以违反接口合同的方式解决您的问题.

请参阅有关适合部分排序的数据结构的此问题.