Shuffle/Random 比较器

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 属性（也是随机的），对于具有相同哈希码和长度的 Strings，它将简单地退回到自然顺序或反向顺序，这不太可能值得注意，因为它只影响这些不常见对的关系。

如果您为没有冲突的值（例如 Integer 实例）或覆盖定义相等性的值的所有属性（例如，x 和 y , of a 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 进行扩展以检查这种情况

Answer 3

这是我的解决方案：

List<String> st = Arrays.asList("aaaa","bbbb","cccc");
System.err.println(st.stream().sorted((o1, o2) -> RandomUtils.nextInt(0, 2)-1).findFirst().get());

Shuffle/Random 比较器

Shuffle/Random comparator

java

sorting

collections

java-8