【算法】撲克隨機洗牌算法分析

一、算法說明

洗牌算法實際上就是常見的隨機問題。我們可以抽象理解為:得到一個M以內的所有自然數的隨機順序數組。

【算法】撲克隨機洗牌算法分析

然而怎麼樣操作才是好的洗牌算法呢?我們通常認為得保證概率相等。即洗牌之後,如果能夠保證每一個數出現在所有位置上的概率是相等的。


二、算法實現

算法1:隨機抽取單張牌

① 隨機抽出一張牌

② 檢查這種牌是否被抽取過,如果已經被抽取過,則重新抽取,直到找到沒有被抽取的牌;

③ 重複上述過程,直到所有的牌都被抽取到。

這種算法是比較符合大腦的直觀思維,這種算法有兩種形式:

  1. 每次隨機抽取後,將抽取的牌拿出來,則此時剩餘的牌為(N-1),這種算法避免了重複抽取,但是每次抽取一張牌後,都有一個刪除操作,需要在原始數組中刪除隨機選中的牌(可使用Hashtable實現)。
  2. 每次隨機抽取後,將抽取的符合要求的牌做好標記,但並不刪除;與1相比,省去了刪除的操作,但增加了額外的存儲標誌為的空間,同時導致可每次可能會抽取之前抽過的牌。

弊端:這種解決方案的時間/空間複雜度都不好。

算法2:隨機抽取兩張牌

每次隨機抽出兩張牌交換,交換一定次數後結束。

<code>void shuffle(int* array, int len)  
{
const int suff_time = len;

for (int idx = 0; i < suff_time; i++)
{
int i = rand() % len;
int j = rand() % len;

int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}/<code>

這是一個常見的洗牌算法。 但是如何確定一個合適的交換次數?

假設交換了m此,則某張牌始終沒有被交換的概率為 (n-2)/n * (n-2)/n, … …* (n-2)/n = ((n-2)/n)^m;我們希望其概率小於摸個值,求出m的解.假設概率小於1/1000,對於n=52,m大概為176,實際上遠遠大於數組的長度.

算法3:Fisher–Yates shuffle算法

每次隨機選取一個數,然後將該數與數組中最後(或最前)的元素相交換(如果隨機選中的是最後/最前的元素,則相當於沒有發生交換);然後縮小選取數組的範圍,去掉最後的元素,即之前隨機抽取出的數。重複上面的過程,直到剩餘數組的大小為1,即只有一個元素時結束。

<code>void shuffle(int* array, int len)  
{
int i = len;
int j = 0;
int temp= = 0;

if (i == 0)
{
return;
}

while (--i)
{
j = rand() % (i+1);
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
} /<code>

PS: 更多精選內容資源分享,歡迎關注微信公眾號:『 developer1024 』


分享到:


相關文章: