随机/随机比较器

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

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

在不违反合同的情况下实施真正的“改组比较器”是不可能的。 Comparator合同的一个基本方面是结果是可重现的,因此必须修复特定Comparator实例的顺序。

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

 List ordering=new ArrayList<>(list); Collections.shuffle(ordering); list.sort(Comparator.comparingInt(ordering::indexOf)); 

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


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

 public static Comparator 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 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 ,它将简单地回退到自然或逆序,这不太可能引人注意,因为它只影响这些不常见对的关系。

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

当元素的类型未知时,比前一个答案更通用:

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

也可以在流中使用:

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

可能会以某种方式发生冲突,因此可以使用HashSetUUID扩展以检查此情况

这是我的解决方案:

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