随机/随机比较器

Question

是否有任何方法可以模拟Collections.shuffle的行为，而比较器不容易受到排序算法实现的影响，以确保结果安全？

我的意思是不违反类似的合同等..

Answer 1

这是我的解决方案：

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

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())

可能会以某种方式发生冲突，因此可以使用 UUID 的 HashSet 进行扩展以检查这种情况

Answer 3

在不破坏合同的情况下实现真正的“洗牌比较器”是不可能的。比较器合约的一个基本方面是结果是可重现的，因此必须固定特定比较器实例的顺序。

当然，您可以使用混洗操作预先初始化该固定顺序，并创建一个比较器来准确建立该顺序。例如

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

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

尽管这有点没有意义。很明显，这个比较器不能用于包含不在排序列表中的元素的集合。

或者，您可以使用首先没有排序的值的稳定属性作为排序标准，例如哈希代码。这可以通过稳定但可随机化的转换来增强，例如

public static Comparator<String> randomOrder() {
    ThreadLocalRandom r = ThreadLocalRandom.current();
    int x = r.nextInt(), y = r.nextInt(), z = r.nextInt();
    boolean b = r.nextBoolean();
    return Comparator.comparingInt((String s) -> Integer.reverse((s.hashCode()&x)^y))
      .thenComparingInt(s -> s.length()^z)
      .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违反合同。

请注意，这个＜code＞比较器＜/code＞看起来有点复杂，因为它必须考虑可能的哈希冲突。它将使用＜code＞length＜/code＞属性（也是随机化的），然后对于具有相同哈希码和长度的＜code＞String＜/code>，它将简单地返回到自然或反向顺序，这不太可能被注意到，因为它只影响这些不常见对的关系。

如果为没有冲突的值（例如整数实例）或覆盖定义相等的值的所有属性（例如，点的 x 和 y）创建这样的比较器，则比较器看起来会简单得多。