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>定义如下：

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;
   }
}

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

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]之间，按照条件概率分开可以写成：

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

• 当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位的元素，权重为：

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

当列表长度越大、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，这个概率并不适用于任何情况，比如当元素的权重有比较明确可比较的含义时，我们希望这个概率是：

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