一個帶限制條件的均勻洗牌問題
問題描述
說到均勻洗牌問題，大家可能都會想到著名的Fisher–Yates shuffle演算法。這個演算法可以將一個擁有n個元素的數組均勻洗亂。所謂洗亂，實際上是隨機選擇一個排列對n個元素進行重排，而均勻洗亂的含義是，對於所有可能被選取的排列（共n!個），演算法選到其中任意一個的概率都是相等的。
上面的演算法所解決的問題對排列的選取沒有任何的限制，n!個排列中任意一個都可以被用來對數組進行洗亂。而最近，一個基友遇到了一個特殊的均勻洗牌需求，問題是這樣的：
整數1到16從左到右按順序排列，從1開始，每連續4個數字分為一組，共四個組，分別用g1, g2, g3, g4表示。現在希望設計一個演算法對這16個整數進行隨機洗亂，但是需要洗亂之後的結果分成同樣的g1, g2, g3, g4四組後，滿足對於任意的i都有gi和gi的交集為空集，而且每種滿足限制條件的洗亂方式都以相等的概率被選擇。
也就是說，在洗亂的過程中，每一組的四個數都不能被洗亂到之前的組中去。所有可能的n!個排列中，有一部分不滿足限制條件的排列將無法在這個問題中被用來洗亂數字。解決這個問題最簡單的辦法是使用Rejection Sampling方法，即先不考慮限制條件，不斷地對數字進行洗亂，直到某次洗亂的結果滿足限制條件為止。這樣的方法可能需要進行多次洗亂操作才能得到想要的結果，雖然從概率上說，連續多次都沒有得到滿足限制條件的洗亂結果的概率以指數衰減到0，但如果滿足限制的排列數目較小，演算法平均需要進行的洗亂次數會比較大，導致運行時間太長而且性能不可預期，也不夠優雅。那麼有沒有一種只需要洗亂所有數字一次，而且運行時間確定的演算法呢？
在使用幾個簡單的思路嘗試解決這個問題失敗之後，筆者嘗試先將原問題簡化尋找一些思路。
簡化的原問題
在原問題中，每一組中都有四個數字，如果每一組中只有一個數字的話，問題會不會更容易解決？於是問題變成：
整數1到16從左到右按順序排列，從1開始，每個數字各自成為一組，共16個組。現在希望設計一個演算法對這16個整數進行隨機洗亂，但是需要洗亂之後的結果滿足對於任意的數字i都不在其原來的位置上。
似曾相識的感覺。。這和組合數學中著名的歐拉錯排問題關係密切：
考慮一個有n個元素的排列，若一個排列中所有的元素都不在自己原來的位置上，那麼這樣的排列就稱為原排列的一個錯排。
簡化後問題的目標就是設計一個演算法從所有可能的錯排中均等概率地隨機選擇一個出來。
在待排列的數字總共有n個的情況下，可以用遞推的方式得到滿足限制條件的排列個數（也就是所謂的錯排個數），接下來筆者嘗試從遞推式的構造思路出發，用同樣的方式構造一個針對簡化後問題的均勻洗牌演算法。
將生成錯排的過程分為兩個步驟：第一步先考慮n個數字被重排之後的第一個數字，為了不和位置1產生衝突，這個數字不能為1，因此只有n-1種選擇，在選定第一個數字（用head表示）之後，第二步的工作是將剩下的n-1個數字（1, 2, ... , head-1, head+1, ..., n）排列到餘下2到n的位置上：
- 在排列中，n-1個位置都沒有衝突（不存在i被放在position: i），且數字1在position: head
- 在排列中，n-1個位置都沒有衝突（不存在i被放在position: i），且數字1不在position: head
第一類排列中，如果忽略數字1，那麼剩下的n-2個數字剛好是一個歐拉錯排，這樣就建立了一個從第一類排列到n-2個數字的歐拉錯排集合的一一映射，因此第一類排列的數目等於D(n-2)（用D(n)表示對n個數字進行錯排的方式數目）。
第二類排列中，數字1不在position: head上，因此將數字1直接替換成數字head將不會產生衝突，替換之後得到的排列是一個對n-1個數字的歐拉錯排，這樣就建立了一個從第二類排列到n-1個數字的歐拉錯排集合的一一映射，因此第二類排列的數目等於D(n-1)。
對於head的n-1種選擇，第二步中對剩下數字的排列方式數都是相等的，即D(n-1)+D(n-2)。這裡可以啟發我們構造出一種以等概率生成錯排的演算法，只需要首先隨機等概率地從2到n中選取一個數字head作為結果的第一個數字，然後以概率D(n-2)/[D(n-1)+D(n-2)]將數字1放到position: head, 最後再遞歸地對剩下的n-2個數字進行錯排；對於數字1沒有被放到position: head的情形，只需要遞歸地對除head之外的n-1個數字進行錯排，最後將得到的錯排中的head替換成1即可。
於是，我們得到了一個能夠等概率隨機生成錯排的演算法。
回到原問題
在原問題中，需要隨機生成的是一種廣義的錯排，它不僅要求數字i在排列後不能留在原位置，還要求數字i不能留在原來的組中。下圖是一個合法的排列：
所以一個直接的想法是，如果我們能夠將原問題對16個數字的排列拆分成4次如上對4個數字的錯排，就有可能通過上一節得到的演算法來解決原問題。首先需要考慮的問題是，這樣的拆分是否總是存在？從g1, g2, g4, g4中各取出一個數字是容易的，但是被取出的4個數字不一定剛好在原來的四個組中各自存在一個（例如排列後的5,1,2,4，1, 2, 4都在g1中）。
為了解決存在性的問題，筆者嘗試使用二分圖對數字洗亂的方式進行描述：將上圖中的每個組都視為二分圖中的一個節點，總共8個節點，如果gi中有k個數字被洗亂到了gj中，那麼在gi和gj之間連一條權重為k的無向邊，代表這k個數字的洗亂方式，這形成一個帶權的二分圖。上圖中數字洗亂方式對應的二分圖如下圖所示：
給定一個二分圖G，在G的一個子圖M中，M的邊集{E}中的任意兩條邊都不依附於同一個頂點，則稱M是一個匹配。
從匹配的定義可以看到，通過擁有四條邊的匹配選取的4個數字無論在洗亂前還是洗亂後都在四個組中每組存在剛好一個。現在的問題是，對於任意的合法洗亂方式，是不是總能在對應的二分圖中找到擁有四條邊的匹配呢？幸運的是這總是可以做到的，證明可以利用圖論中著名的K?nigs theorem：
在二分圖中，最大匹配數等於最小點覆蓋數。
簡單來說，最大匹配數指的是所有匹配中包含的邊的條數最多的那個匹配包含的邊數，在這裡我們希望證明存在一個擁有四條邊的匹配，這隻需要證明最大匹配數等於4即可，根據K?nigs theorem，這隻需要證明最小點覆蓋數等於4。點覆蓋是一些圖中節點的集合，它們使得圖中任何一條邊都至少和點覆蓋集合中的某個點關聯，最小點覆蓋數，就是滿足這個條件的點覆蓋集合中，包含點最少的點覆蓋所擁有點的數目。考慮到每個節點關聯到的所有邊的權值之和等於4，因此點覆蓋中的任意一個點關聯到的邊權值之和不會超過4；而所有邊的權值之和等於16，這意味著點覆蓋中至少包含4個節點，而這樣的點覆蓋是顯然存在的（選取所有gi即可），因此最小點覆蓋數等於4。
這保證了我們總可以從16個數字中拆分出4個來進行錯排。在剩下的12個數字中，同樣的操作可以繼續進行（這一點也是需要證明的，但證明的過程和上面完全相同），從而拆分出下一次需要進行錯排的4個數字。拆分後的四次錯排完成之後，我們就得到了一個滿足原問題限制條件的洗亂方式。
用這樣的演算法去隨機洗亂數字，一趟操作得到的洗亂結果都會是滿足原問題限制條件的；而從上面的證明，可以肯定任意一種滿足原問題限制的洗亂方式，一定可以通過這個演算法對16個數字拆分成4次操作得到。
到目前為止，我們至少得到了一個能在一趟操作後隨機生成一個合法排列的演算法。在這個演算法中，每一個合法排列都能有機會被生成出來。
原問題並沒有解決
上面的演算法可以用一趟操作產生一個合法的排列，但是，所有合法排列被生成的概率卻不是均等的（但可以保證所有合法排列被生成的概率都不為0）。其原因是因為一個合法的排列在該演算法中可能可以通過多種拆分方式得到，雖然每種拆分方式下的合法排列都是等概率被生成的，但是不同的拆分方式數目將對最後的概率分布造成偏差，這一點還沒有解決。目前筆者已經對這個問題失去了耐心，寫成知乎日誌記錄一下整個過程，之後有時間再想吧。有知乎大神碰巧看到這個問題知道更好的方法和思路的話，希望能告知筆者，謝謝~
推薦閱讀：