一個重新排列的演算法，如何計算每種排列的概率？

01-06

Unity - Manual: Adding Random Gameplay Elements
Shuffling a List這一節下介紹的演算法：
遍曆數組，每次把一個元素同一個隨機的元素交換位置。
代碼如下：
void Shuffle (int[] deck) { for (int i = 0; i &< deck.Length; i++) { int temp = deck[i]; int randomIndex = Random.Range(0, deck.Length); deck[i] = deck[randomIndex]; deck[randomIndex] = temp; } }
似乎這樣生成的排列不是等概率的，請問如何計算每種排列的概率？

講道理，這個演算法是有問題的。

這個演算法流程中，共調用了 $n$ 次隨機數生成，每次隨機數的選擇範圍是 $0$ 到 $n-1$ ，也就是說，程序實際執行過程會有 $n^n$ 種可能的情況分支。

而 $n$ 個元素的全排列是 $n!$ 種， $n!$ 如果不能整除 $n^n$ 就意味著生成的排列不是等概率的。

換言之，這個演算法的實際流程就像一個深度為 $n$ 的 $n$ 叉樹從根到葉子結點的路徑，葉子結點有 $n^n$ 個。可能會有多個葉子結點對應同一種全排列，如果演算法正確，根據對稱性，每種全排列對應的葉子結點數應該是一樣多的。如果 $n!$ 如果不能整除 $n^n$ ，那麼演算法就有問題。

正確的做法是

int randomIndex = Random.Range(i, deck.Length);

Unity這個doc的這段代碼是一個經典演算法的經典錯誤實現。。。

最近剛好刷到隨機演算法， @白如冰修正後的代碼就是Fisher-Yates演算法，題主貼出來的代碼實現是帶有bias的。

題主的問題是：了解這段代碼生成的排列不是等概率的，現在問每個排列的概率如何求。

首先贊一下題主是個熱愛思考的人，這個問題還是挺有意思的。

對於一個含有7個元素的list，概率分布如下圖：

觀察發現，這個矩陣是對稱的；並且，對於第k個元素，最終位置為k-1的可能性是最高的。嗯，這個回答是不是不那麼滿意？所以概率到底是怎麼算出來的啊？╯°□°）╯︵ ┻━┻

好吧，我們可以利用分析馬爾可夫鏈的方法來分析這個問題，將每一步的交換完成後出現的狀態的概率用轉移矩陣來描述：

假設list裡面一共有N個元素，設矩陣 $A_k$ 中每個元素 $A_k(i,j)$ 表示在第k步時i位置上的元素換到了j位置的概率。那麼，第k次交換時，當 $i=k$ 或者 $j=k$ 時， $A_k(i,j) = 1/N$ ；對於其他所有的 $i e k$ ， $A_k(i,i) = (N-1)/N$ ，因為除了被選中作交換的元素其他元素都留在原位；矩陣中其他元素均為0。而最終我們所求的概率分布就是所有這些矩陣 $A_1.....A_N$ 的乘積。

詳細分析描述見 algorithm - What distribution do you get from this broken random shuffle?。

下圖是在Mathematica中畫出的，當元素個數為100時的概率分布圖：

PS: 我特意去看了一眼問題編輯日誌，發現問題自7月1日題主發布後並沒有被修改，然而為何大家回答都跑偏了呃。。。

如果隨機數發生器是理想的，@白如冰大大提供的演算法可以使生成的每種排列的概率均為 $frac{1}{n!}$

採用數學歸納法：

考察生成的一個排列

$a_{0}, a_{1},...,a_{n-1}$

1.第一步就位的元素 $a_{0}$ 由整個向量中的某一元素交換得到，此元素選取的概率為 $frac{1}{n}$

2.假設對於前k個元素，都是以 $frac{1}{n}$ 的概率得到的。

3.對於第k+1個元素，是從 $[k+1,length)$ 中隨機抽取的，每個元素被抽取的概率是 $frac{1}{length-k-1}$ 。但是， $[k+1,length)$ 中的元素實際上是由前k次交換生成的，由於2中的假設，原向量中的元素，都有 $frac{length-k-1}{length}$ 的概率進入到 $[k+1,length)$ 中去。所以原向量中的每個元素變為生成向量中第k+1個元素的概率是 $frac{length-k-1}{length} imes frac{1} {length-k-1}$ ，即 $frac{1}{length}$

由於原向量中各元素出現在生成向量中的各位置的概率相等，所以生成排列的概率應相等，為 $frac{1}{n!}$

但是，由於偽隨機數發生器實現的演算法，並不能保證獲得n個獨立的隨機數。所以此演算法事實上並不能獲得所有的排列。

參考文獻：

鄧俊輝《數據結構習題解析》

貼兩個老鏈接，雖然提的這個問題是原問題的子問題，但分析里也解釋的很清楚了。

Problem:

https://code.google.com/codejam/contest/2984486/dashboard#s=p2a=2

Analysis:

https://code.google.com/codejam/contest/2984486/dashboard#s=aa=2

一種方法當然是首先弄一個數池，池中有1~n的數字，然後每次以等概率選出一個並從池中移除。

另外MATLAB的randperm提供了一個巧妙的思路：隨機產生n個均勻分布的隨機數，並且依次給每個數賦以1~n的序號，然後對齊進行排序，排序後的序號序列就是一個隨機排列。當然，這樣做是否是嚴格等概率的倒是沒細究過，不過直覺上很符合隨機排列序列的需要，儘管在概率統計中「直覺」很不靠譜……

感謝 @白如冰指出我之前回答不對

因為我只列出來每一次循環可能的結果，這些可能的結果概率相等，但是忽略了那些不可能出現的結果的概率，比如i=1時，從1，2，3不會變成3，1，2，也就是說每一步之後的所有結果的概率分布不一致，（但是有兩個取值，0和一個非零的數）,這導致了循環結束之後，不同結果的概率不一致。

------------------------------------------------------------------

We can consider a very simple case where the length of the array is 2.

Suppose the initial state of the array = [1,2].

After the first iteration there are two possible outcomes, i.e., [1,2] and [2,1], with equal probabilities (0.5).

And for either outcome, after the second iteration, there are also two possible outcomes, i.e., [1,2] and [2,1], still with equal probabilities.

For n=3:

initial state [1,2,3]

after the first iteration:

[1,2,3] with probability of 1/3

[2,1,3] with probability of 1/3

[3,2,1] with probability of 1/3