Re: [心得] 亂數不重複的方法

[yoco315 (眠月)]

假設要從十張裡面抽出三張
我們就知道每張牌被抽出來的機率是 3/10
所以就可以這樣寫

for ( size_t i=0; i<10; ++i ) {
    if ( rand() % 10 < 3 ) {            // 小於 3 代表被選中
        cout << i ;
    }
}

但是這樣有個問題是，被選出來的不一定是三張，
可能是 0 張，也可能是 10 張，雖然說平均是 3 張沒錯。
所以我們要在這個過程控制一下，試考慮一個狀況：

當我第一張的 rand()%10 就小於 3 被選中，
那剩下的 9 張裡面其實只能有兩張被選中，
所以之後的每張牌其實機率就不是 rand()%10 < 3，
而是 rand()%9 < 2，因為剩下的九張牌裡面每個人中獎的機會是 2/9。
又，假設繼續選選選選到第 9 張，總共有兩張被選中，
還有一張沒出來，那最後一張被選中的機率就一定會是 1/1。
利用這種機率控制的方法，就可以讓抽完的牌數一定是 3。

所以我們需要記住兩個值，
1. 已選出多少牌：n
2. 還剩下多少牌：這個可以用 10 - i 得到

for ( size_t i=0; i<10; ++i ) {
    if ( rand() % (10-i) < (3-n) ) {
        ++ n ;
        cout << i ;
    }
}

空間複雜度 O(1)，時間複雜度 O(總牌數)。
當總牌數遠大於要抽出牌數的話，這個方法就不適用。

--
To iterate is human, to recurse, divine.
遞迴只應天上有, 凡人該當用迴圈.              　   L. Peter Deutsch

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.45.107.213
推 FRAXIS:為甚麼總牌數遠大於要抽的牌數就不適用？
→ akasan:m/n n=總 m=抽 當n>m很多時抽出來機率就小 => O(n)
推 s3748679:學到好方法^^..，收藏起來。
推 FRAXIS:回二樓  但是有什麼演算法 可以不用看過全部的牌
→ FRAXIS:卻可以保證取出來的牌是均勻分配？
推 FRAXIS:Sorry 我搞錯了.. 當我沒問
→ ykjiang:這段程式似乎有 BUG ，沒人看出來嗎？
→ ykjiang:原來是我看錯了...