Java 中的 Collection.shuffle(List<?> list)是一个可以将 List 中的元素随机打散的函数，但是在有些场景下，我们需要打散排好序的 List，比如有一组用户可能感兴趣的商品列表，用户可能多次看到这个列表，希望每次看到时列表的顺序是不同的。这就会用到 weighted shuffle 算法，既希望进行随机打散，又希望在 shuffle 的过程中能尽可能保持原有顺序。

Collection.shuffle 的实现

Java 从 1.2 开始就引入了 java.util.Collections 这个类，关于shuffle 方法) 的实现是这样描述的：

This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the “current position”. Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.

这个实现将列表反转，从最后一个元素向前到第二个元素，重复随机选取一个元素与当前位置的元素交换。被交换元素是从列表第一个元素到当前元素（包括）的这部分中随机挑选的。

一种 Weighted Shuffle 算法

从 shuffle 扩展

我们可以从 Java Collection.shuffle 实现中交换的想法触发，扩展出一种 weighted shuffle 的算法。在 shuffle 方法中，可以不严格地认为两个元素是否发生交换的概率是 50%，我们只要调整这个概率，让排在有序列表前面的元素与排在后面的元素交换的概率更低就可以实现 weighted shuffle 了.

比如，有序列表是一个 List<WeightItem<E>> 类型的，WeightItem<E>定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class WeightItem<E> {
   private E item;
   private Double weight;
       
   public WeightItem(E item, Double weight) {
       this.item = item;
       this.weight = weight;
   }

   public E getItem() {
       returnthis.item;
   }
     
   public Double getWeight() {
       return this.weight;
   }
}

这样就可以写出最核心的代码了

1
2
3
4
5
Collections.sort(weightItemList, new Comparator<WeightItem>(){	
  public int compare(WeightItem s1, WeightItem s2){
      return Math.random() * s1.getWeight() > Math.random() * s2.getWeight() ? -1 : 1;
  }
});

由于我们直接使用了 Collections 中的 sort 方法，所以这个 weighted shuffle 算法的空间复杂度是O(n)，时间复杂度是O(nlogn)。

概率有多大？

前面提到 weighted shuffle 是介于完全随机和完全保序之间，两个元素交换的概率到底有多大，我们可以算一算。

假设有序列表中两个元素 Xm 和 Xn，它们的权重分别是 M 和 N，不妨设 M >= N，打散后 Xm 排在 Xn 后面的概率就等同于下面这个更数学化的描述：

设随机变量 m 服从 [0, M] 之间均匀分布，随机变量 n 服从 [0, N] 之间均匀分布，M >= N，求 p(m < n)。

m 可能在 [0, N] 之间，也可能在 [N, M] 之间，按照条件概率分开可以写成：

p(m < n) = p(m < n | m > N) p(m > N) + p(m < n | m <= N) p(m <= N).

上式中第一项为 0，第二项 p(m <= N)=N / M，而当 m <= N 时，m 的取值范围与 n 相同，所以 p(m < n | m <= N) = 1 / 2。所以：

p(m<n) = N / 2M.

  • 当 N = M 时，p(m < n) = 0.5，元素 Xm 和 Xn 的权重相同，Weighted Shuffle 退化成普通的 shuffle，元素间的交互是完全随机的；
  • 当 N = 0 是，p(m < n) = 1，元素 Xm 和 Xn 的顺序始终可以保持，不再是 shuffle 了。

更随机？还是更保序？

在对一个有序列表进行 weighted shuffle 的时候，我们面临两个方向的选择，让 shuffle 的结果更加随机，或者让结果更保持原有的顺序。这个问题通过对有序列表元素设置权重来完成。

如果我们只是有一个有序列表，而没有每个元素对应的权重，有一种简单设置权重的方法，对于排列在 i 位的元素，权重为：

w(i) = (L - i + 1) ^ alpha

其中 L 为列表的长度，alpha 为控制偏向随机还是偏向保序的参数，取值范围是[0, +infinite)。我们可以比较排列在第一位和最后一位的两个元素在 shuffle 后交换顺序的概率：

p = 1 / (2 * L^alpha)

当列表长度越大、alpha 取值越大时，概率越小；反之概率越大。

为了直观展示参数的效果，这里列出几个例子：

L alpha p
5 0.01 50.8%
5 0.1 57.4%
5 1 90.0%
10 0.01 51.1%
10 0.1 60.3%
10 1 95.0%
30 0.01 98.3%
30 0.1 64.6%
30 1 51.7%

最后：还是概率

本文的算法给出两个有序元素 shuffle 后的顺序改变的概率是 p(m<n) = N / 2M，这个概率并不适用于任何情况，比如当元素的权重有比较明确可比较的含义时，我们希望这个概率是：

p(m<n)=N / (N + M).

对于这种情况，我们只要修改 weighted shuffle 算法中对排序交换条件的判断代码就可以实现了，具体做法这里就不做详细的介绍了。