Java中的Collection.shuffle(List<?> list)是一個可以將List中的元素隨機打散的函數(shù)，但是在有些場景下彩扔，我們需要打散排好序的List铣卡，比如有一組用戶可能感興趣的商品列表主经，用戶可能多次看到這個列表腻异，希望每次看到時列表的順序是不同的。這就會用到weighted shuffle算法取试，既希望進行隨機打散悬槽，又希望在shuffle的過程中能盡可能保持原有順序。
Collection.shuffle的實現(xiàn)
Java從1.2開始就引入了java.util.Collections這個類瞬浓，關(guān)于shuffle方法的實現(xiàn)是這樣描述的：
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.
這個實現(xiàn)將列表反轉(zhuǎn)初婆，從最后一個元素向前到第二個元素，重復(fù)隨機選取一個元素與當前位置的元素交換猿棉。被交換元素是從列表第一個元素到當前元素（包括）的這部分中隨機挑選的磅叛。
一種Weighted Shuffle算法
從shuffle擴展
我們可以從Java Collection.shuffle實現(xiàn)中交換的想法觸發(fā)，擴展出一種weighted shuffle的算法铺根。在shuffle方法中宪躯，可以不嚴格地認為兩個元素是否發(fā)生交換的概率是50%，我們只要調(diào)整這個概率位迂，讓排在有序列表前面的元素與排在后面的元素交換的概率更低就可以實現(xiàn)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算法的空間復(fù)雜度是O(n)臣缀，時間復(fù)雜度是O(nlogn)。
概率有多大泻帮？
前面提到weighted shuffle是介于完全隨機和完全保序之間精置，兩個元素交換的概率到底有多大，我們可以算一算锣杂。
假設(shè)有序列表中兩個元素Xm和Xn脂倦，它們的權(quán)重分別是M和N，不妨設(shè)M >= N元莫，打散后Xm排在Xn后面的概率就等同于下面這個更數(shù)學(xué)化的描述：
設(shè)隨機變量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的權(quán)重相同，Weighted Shuffle退化成普通的shuffle打却，元素間的交互是完全隨機的杉适；
- 當N = 0是，p(m < n) = 1柳击，元素Xm和Xn的順序始終可以保持猿推，不再是shuffle了。
更隨機捌肴？還是更保序蹬叭？
在對一個有序列表進行weighted shuffle的時候，我們面臨兩個方向的選擇状知，讓shuffle的結(jié)果更加隨機秽五，或者讓結(jié)果更保持原有的順序。這個問題通過對有序列表元素設(shè)置權(quán)重來完成饥悴。
如果我們只是有一個有序列表坦喘，而沒有每個元素對應(yīng)的權(quán)重盲再，有一種簡單設(shè)置權(quán)重的方法，對于排列在i位的元素瓣铣，權(quán)重為：
其中L為列表的長度答朋，alpha為控制偏向隨機還是偏向保序的參數(shù)，取值范圍是[0, +infinite)棠笑。我們可以比較排列在第一位和最后一位的兩個元素在shuffle后交換順序的概率：
當列表長度越大梦碗、alpha取值越大時，概率越斜途取洪规；反之概率越大。
為了直觀展示參數(shù)的效果循捺，這里列出幾個例子：
| 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斩例，這個概率并不適用于任何情況，比如當元素的權(quán)重有比較明確可比較的含義時巨柒，我們希望這個概率是：
對于這種情況樱拴，我們只要修改weighted shuffle算法中對排序交換條件的判斷代碼就可以實現(xiàn)了，具體做法這里就不做詳細的介紹了洋满。
