我有一個1*n的格子帶，上面有n個單位格子，需要把其中m個格子染上色。我現在有三種演算法，哪種符合要求？

01-26

我有一個1*n的格子帶，上面有n個單位格子，需要把其中m個格子染上色。要求是：
1. 每個格子都是m/n概率被染色；
2. 格子帶總共有C(n,m)個染色狀態，都是等概率的，即都是1/C(n,m)
已經有一個能隨機均勻生成[1,n]的隨機數生成器getrand(1,n)
演算法1：從左往右考慮每個格子，對於第i個格子(i=1,2,3,...,n)，隨機生成一個[1,n-i+1]的整數，如果小於等於p，那麼這個格子被染上色其中p為剩餘需要染色的數目

演算法2：隨機一個[1,n]的整數x，如果這個格子x已經被染色，那麼重新生成一個整數，直到隨機到一個沒有被染色的格子，然後把格子x染色。執行m次。
演算法3：令前m個格子都染色，然後從左往右考慮每個格子，對於第i個格子(i=1,2,3,...,n)，隨機生成一個[1,i]的整數x(感謝答主指出問題)，把第x個格子與第i個格子交換。
請問這三種演算法中有沒有符合要求的？希望給出證明？或者有沒有別的演算法？

演算法2的正確性是明顯的。

對於演算法3，我們可以發現第n個格子被選擇的概率是 $frac m{n-1}$ ，因此是錯誤的。但是如果將生成一個 $[1,i-1]$ 中的隨機數改為生成一個 $[1,i]$ 中的隨機數，則這個演算法可以等概率的生成 $1$ 到 $n$ 所有的排列，因此也是正確的。

注意到演算法2在最壞情況下無法得出結果，而演算法3需要 $O(n)$ 的空間。而對於題目的問題，存在一個需要線性時間與 $O(m)$ 複雜度的演算法滿足要求。過程大概是這樣的：

令 $S$ 為選擇的格子的集合。初始時， $S={1,2ldots ,m}$ 。從第 $m+1$ 個格子開始，從左往右考慮每個格子。對於第 $i$ 個格子，有 $frac mi$ 的概率將其與 $S$ 中的一個隨機元素交換。則當演算法結束時， $S$ 就是一個符合條件的隨機的選擇。

寫的有點長。。三個演算法都可以滿足要求，證明如下。

設 $A_i$ 為事件第ｉ個格子被染色的示性隨機變數，即該事件發生時 $A_i=1$ ，否則 $A_i=0$ 。

如果對於任意包含且只包含ｍ個１的數列 $T=[t_1, t_2, ...,t_n]in{0,1}^n$ ，都有 $Pleft(igcap_{i=1}^nA_i=t_i ight)=frac{1}{C_n^m}$ ，則該演算法符合要求，因此下面針對每一種演算法證明有上式成立。

演算法一根據如下規則逐一對隨機變數進行採樣：

$P(A_1=1)=frac{m}{n}$

$P(A_i=1|A_1, ..., A_{i-1})=frac{p}{n-i+1}=frac{m-sum_{j=1}^{i-1}A_j}{n-i+1}$

則對於任意給定數列 $T=[t_1, t_2, ...,t_n]in{0,1}^n$ ，我們有

$Pleft(igcap_{i=1}^nA_i=t_i ight)$ $=P(A_1=t_1)prod_{i=2}^{n}P(A_i=t_i|igcap_{j=1}^{i-1}A_j=t_j)$

上式為ｎ個分式的乘積，分母的乘積等於 $n!$ ，分子的乘積分為兩類，對應 $t_i=1$ 的分式的分子的乘積為 $m!$ （需要被染色的格子的個數從ｍ下降到１），其餘的乘積為 $(n-m)!$ （不需要被染色的格子的個數從ｎ－ｍ下降到１）。因此乘積為 $frac{m!(n-m)!}{n!}=frac{1}{C_n^m}$ 。演算法一得證。

演算法二基於Rejection sampling，可以保證每一輪以均等的概率從沒有染過色的格子中選擇一個進行染色。這裡一輪定義為：重複生成［１，ｎ］的隨機數，直到該隨機數對應的格子沒有被染色。因此也滿足條件。但當ｍ和ｎ接近時效率會比較低。

演算法三的證明可以基於數學歸納法。對命題『對於任意ｎ和 $mle n$ ，任意給定只含有ｍ個１的數列 $T=[t_1, t_2, ...,t_n]in{0,1}^n$ 都有均等概率 $Pleft(igcap_{i=1}^nA_i=t_i ight)=frac{1}{C_n^m}$ 』中的ｎ進行歸納。

１、當ｎ＝１時，無論ｍ取０還是１，結果都只有一種，因此概率是均等的。

２、假設命題對ｎ＝ｋ－１成立，考慮ｎ＝ｋ的情況。

２.１、當ｍ＝ｋ時，只有一種塗色情況，因此概率必然是均勻的。

２.２、當ｍ＜ｋ時，首先執行該演算法的前ｋ－１個步驟，根據假設可知，我們已經以均等的概率從前ｋ－１個格子中選擇了ｍ個進行染色，即對於任意包含ｍ個１的數列 $T^-=[t_1, t_2, ...,t_{k-1}]$ ，都有 $Pleft(igcap_{i=1}^{k-1}A_i=t_i ight)=frac{1}{C_{k-1}^m}$ 。

對於第ｋ次操作，我們可能以１－ｍ／ｋ的概率把第ｋ個格子與一個沒有染色的交換，因此對於包含ｍ個１的數列 $T_0=[t_1, t_2, ...,t_{k-1},0]$ ，我們有

$Pleft(igcap_{i=1}^{k}A_i=t_i ight)=Pleft(igcap_{i=1}^{k-1}A_i=t_i ight)frac{k-m}{k}$ $=frac{1}{C_{k-1}^m}frac{k-m}{k}=frac{1}{C_{k}^m}$ 。

我們還有可能以ｍ／ｋ的概率把第ｋ個格子與前面一個染過顏色的進行交換，因此對於包含ｍ個１的數列 $T_1=[t_1, t_2, ...,t_{k-1},1]$ ，我們有

$Pleft(igcap_{i=1}^{k}A_i=t_i ight)=frac{k-m}{C_{k-1}^m}frac{1}{k}=frac{1}{C_{k}^{m}}$

（解釋一下，就是說前ｋ－１次操作，得到的結果恰好比 $T^-$ 多了一個１，概率為乘積中的第一項，然後最後一次操作恰好又把多的那個１選走了，概率１／ｋ）

綜合 $T_0$ 和 $T_1$ 兩類情況可知ｎ＝ｋ時原命題成立，根據數學歸納法可知演算法三是正確的。

題目可以抽象為：

在[1，n]個數字中，隨機取出m個數字。

可以採用與洗牌演算法（Fisher-Yates shuffle）類似的方法獲取。

不同之處為：洗牌演算法是隨機找到一個排列，題中問題是隨機找到一個組合。

這種演算法與題主給出的演算法3基本一致。

《演算法導論》P129頁課後題5.3-7

suppose we want to create a random sample of the set {1,2,3,…,n}, that is, an m-element subset S, where 0≤m≤n, such that each m-subset is equally likely to be created. One way would be to set A[i]=i for i=1,2,3,…,n, call RANDOMIZE-IN-PLACE(A), and then take just the first m array elements. This method would make n calls to the RANDOM procedure. If n is much larger than m, we can create a random sample with fewer calls to RANDOM. Show that the following recursive procedure returns a random m-subset S of {1,2,…,n}, in which each m-subset is equally likely, while making only m calls to RANDOM:

RANDOM-SAMPLE(m,n) if m == 0 return ? else S = RANDOM-SAMPLE(m-1, n-1) i = RANDOM(1,n) if i ∈ S S = S ∪ {n} else S = S ∪ {i} return S

翻譯過來就是：n個數隨機等概率的取樣m個。

該題的證明方法1：http://clrs.skanev.com/05/03/07.html

該題的證明方法2 ：http://www.cnblogs.com/Jiajun/archive/2013/05/15/3080111.html

原帖地址：【演算法導論學習-012】n個數隨機等概率的抽樣m個 - 博客頻道 - CSDN.NET

1,2對，3不對。

3中把x in [1,i-1]改成[1,i]就對了，其中x=i時表示此時不交換。

我先給出一種演算法0吧：

隨機生成一個排列{p_n}（這n!種排列出現概率皆為1/(n!)），然後對於所有滿足pi&<=m的格子染色。這個正確性顯然。

演算法1，2，以及修改後的3皆可被看成生成排列的演算法。

偽代碼見http://paste.ubuntu.com/23815324/知乎沒縮進很難受。