随机/随机比较器

Question

有没有办法模拟Collections.shuffle的行为而没有比较器易受排序算法实现的影响,结果是安全的？

我的意思是不打破可比合同等.

Answer 1

在不违反合同的情况下实施真正的"洗牌比较器"是不可能的.Comparator合同的一个基本方面是结果是可重复的,因此Comparator必须修复特定实例的排序.

当然,您可以使用混洗操作预先初始化该固定排序,并创建一个比较器,该比较器将精确地建立此排序.例如

List<ElementType> ordering=new ArrayList<>(list);
Collections.shuffle(ordering);

list.sort(Comparator.comparingInt(ordering::indexOf));

虽然这有点无意义.很明显,这个比较器不能用于包含不在ordering列表中的元素的集合.

或者,您可以使用首先没有排序的值的稳定属性作为排序条件,例如哈希码.这可以通过稳定但随机化的变换来增强,例如

public static Comparator<String> randomOrder() {
    ThreadLocalRandom r = ThreadLocalRandom.current();
    int x = r.nextInt(), y = r.nextInt();
    boolean b = r.nextBoolean();
    return Comparator.comparingInt((String s)->s.hashCode()^x)
     .thenComparingInt(s->s.length()^y)
     .thenComparing(b? Comparator.naturalOrder(): Comparator.reverseOrder());
}

 

List<String> list=Arrays.asList("hello", "now", "shuffle", "this", "!");
list.sort(randomOrder());
System.out.println(list);
list.sort(randomOrder());
System.out.println(list);

关键点是每个Comparator实例代表一个随机选择但固定的顺序,我们创建一个新Comparator实例来请求不同的排序.因此,不Comparator违反合同.

请注意,这Comparator看起来有点复杂,因为它必须关注可能的哈希冲突.它将使用length属性(也是随机的)然后对于String具有相同哈希码和长度的s,它将简单地回退到自然或逆序,这不太可能引人注意,因为它只影响这些不常见的对的关系.

如果为没有冲突的值(例如Integer实例)创建这样的比较器或覆盖定义相等的值的所有属性(例如,两者,x和ya Point),则比较器看起来会更简单.

Answer 2

当元素的类型未知时，与上一个答案更通用：

public static <T> Comparator<T> shuffle() {
    final Map<Object, UUID> uniqueIds = new IdentityHashMap<>();
    return Comparator.comparing(e -> uniqueIds.computeIfAbsent(e, k -> UUID.randomUUID()));
}

也可以在流中使用：

list.stream().sorted(Streams.shuffle()).collect(Collectors.toList())

有可能是碰撞莫名其妙，所以它可以使用扩展HashSet的UUID检查这种情况下，