C#的解題思路(1)：不重複随機數的産生問題

說明：寫作本文的出發點是最近和一個有3年開發經驗的.NET開發人員聊天，他跟我說經常沒有思路，在實際開發中我也見過一個具有4、5年開發經驗的開發人員幾乎沒有靈活變通的能力，是以打算寫一系列文章，在這個系列文章中我會主要講解解題的思路，而不是講述什麼新技術新特性，借這個系列文章為國中級開發者了解遇到問題别人是如何思考和解決的。當然，如果你的思路比本文提到的更好，歡迎指出來，同時如果你對本系列文章有更好的建議或者有日常中的一些典型問題，請給我聯系，我們共同探讨。目前我暫時能想到的有不重複随機數産生問題、字元串與數值轉換的問題、特殊的資料庫鎖問題、訪客來路追蹤問題、線上使用者統計問題、統計使用者通路頁面偏好問題。

好了，我現在開始本篇的講述。本篇的最原始形态是來源于我早年做的一個Java SE應用軟體，它是用來模拟彩票投注站的選好軟體的。應為在早年Java SE中用swing做界面布局是一件比較痛苦的事情，是以後來我重新用C#做了一個。這個問題的原型就是解決雙色球随機選号的問題，我們知道雙色球紅色球共包含1到33這33個紅色号碼球及1到16這16個藍色号碼球，一注雙色球号碼應包括6個紅色球号碼和1個藍色球号碼。藍色号碼球很好解決，随機從1到16這16個數字中随機選取一個就行了。但是紅色球就存在這樣一樣問題，每次選取的紅色球不能與本注中已經選取的号碼重複，這個問題歸結為生成不重複随機數問題。

在本篇我就怎麼生成不重複的紅色球展開讨論。

解題思路一

在早期的Java中不包含泛型，隻能使用ArrayList，是以我是用ArrayList來實作的。在Java中的ArrayList和C#中的ArrayList在用法上是很相似的（這就是為什麼高手經常說掌握一門語言之後再去掌握另一門語言是很容易的事情，應為思想是相通的，呵呵）。在這裡我最想想到的就是使用循環，每次循環中随機生成一個随機數，判斷一下這個随機數是否已經在本注中使用，如果沒有使用就将這個号碼儲存到結果中去，反之則進行下一輪循環，循環的結束條件就是生成了滿足要求的6個數字。接觸到泛型之後，我知道在這裡我所使用的資料類型是int類型（當然也可以使用byte類型），如果使用ArrayList儲存int這樣的值類型資料會存在着裝箱和拆箱操作，帶來不必要的性能損失，是以針對這種集合中資料類型單一的情況可以考慮泛型集合，于是得到了下面的代碼：

/// <summary>

/// 從1到33中任意選取不重複的6個随機數

/// </summary>

/// <returns></returns>

public List<int> GenerateNumber1()

{

//用于儲存傳回的結果

List<int> result = new List<int>(6);

Random random = new Random();

int temp = 0;

//如果傳回的結果集合中實際的元素個數小于6個

while (result.Count < 6)

{

//在[1,34)區間任意取一個随機整數

temp = random.Next(1, 34);

if (!result.Contains(temp))

{

//如果在結果集合中不存在這個數，則添加這個數

result.Add(temp);

}

}

//result.Sort();//對傳回結果進行排序

return result;

}

當然，上面這種思路是可以實作的，但是每次随機生成一個随機數都要判斷在結果集合中是否已經存在這個數，如果存在還要繼續下一個循環，這樣一來并不是每一輪循環都能生成一個有效（即不重複）的随機數，并且result.Contains(temp)盡管看起來隻有一句，但實際在内部還是要通過循環來判斷，效率還是較低。假如有一天有個人看到這篇文章，他想：很好，我終于可以試試了，我要從1到10000個數中取出9999個不重複的随機數，用上面的這個方法，可能很長時間都得不到結果（不要以為沒有這樣的人，我就遇見多多次不會變通的人，實際上最好的解決辦法就是從10000中随機去掉一個就可以了，而不是照搬上面的套路）。

解題思路二

剛才說到在方法一中并不是每一輪循環都能生成一個有效的、不重複的随機數，那麼有沒有這樣的辦法，保證每一輪循環都能生成一個有效地、不重複的随機數呢？答案是有的。

具體做法是這樣的，我們将初始化一個容器集合，在這個容器集合中包含了所有可能的值，然後每次随機從這個容器集合中随機選取一個值儲存到結果集合中去，之後我們就從容器集合中将這個已經使用過的值删除掉，然後再進行下一輪的循環。既然都已經從容器集合中删除掉了，自然在下一輪循環中随機從容器集合中取一個值，這個值自然不會重複了。因為這個集合的容量是可變的，那麼自然也是使用泛型集合了，代碼如下：

/// <summary>

/// 從1到33中任意選取不重複的6個随機數

/// </summary>

/// <returns></returns>

public List<int> GenerateNumber2()

{

//用于存放1到33這33個數

List<int> container = new List<int>(33);

//用于儲存傳回結果

List<int> result = new List<int>(6);

Random random = new Random();

for (int i = 1; i <= 33; i++)

{

container.Add(i);

}

int index = 0;

int value = 0;

for (int i = 1; i <= 6; i++)

{

//從[0,container.Count)中取一個随機值，保證這個值不會超過container的元素個數

index = random.Next(0, container.Count);//謝謝熱心朋友指出這裡的錯誤

//以随機生成的值作為索引取container中的值

value = container[index];

//将随機取得值的放到結果集合中

result.Add(value);

//從容器集合中删除這個值，這樣會導緻container.Count發生變化

container.RemoveAt(index);

//注意這一句與上面一句能達到同樣效果，但是沒有上面一句快

//container.Remove(value);

}

//result.Sort();排序

return result;

}

經過這麼一改動，确實能做到每次循環都能生成一個唯一的有效的不重複的數，這樣一來就能做到在M個數中選取N個數時隻需要循環M×N次就可以了（M＞N，并且都是正整數）。不過也有人會說，我現在還在維護一個.NET1.1的項目，我這裡也有類似的需求，可是在.NET2.0以下版本中是沒有泛型的，你能給我想個辦法嗎？我的答案是可以的。

解題方法三

在這個方法中我們不适用泛型集合，隻使用數組，這樣一來這種做法就可以适用于C、Java、PHP等語言和.NET1.1中了。

思路如下，首先使用一個數組作為存儲所有可能值的容器集合，然後通過循環每次生成一個随機值，這個值将來會作為下标來通路容器集合中的數值。因為數組是不可變集合，我們不能将已經使用數值從數組中删除，并且它們是簡單的資料類型我們不可能給每個數值增加一個屬性表示數值是否已經被使用過了，那該怎麼辦呢？辦法就是每次從可用的下标集合中随機生成一個值，然後以這個值作為索引從容器集合中得到相應的值儲存到結果集合中，除此之外再将這個已經使用過的值與數組中最後一個沒有使用到的值互換位置，然後下一輪再在所有沒有使用過的值中重新再取一個值。代碼如下：

public int[] GenerateNumber3()

{

//用于存放1到33這33個數

int[] container = new int[33];

//用于儲存傳回結果

int[] result = new int[6];

Random random = new Random();

for (int i = 1; i <= 33; i++)

{

container[i - 1] = i;

}

int index = 0;

int value = 0;

for (int i = 0; i < 6; i++)

{

//從[1,container.Count + 1)中取一個随機值，保證這個值不會超過container的元素個數

index = random.Next(1, container.Length-1-i);

//以随機生成的值作為索引取container中的值

value = container[index];

//将随機取得值的放到結果集合中

result[i]=value;

//将剛剛使用到的從容器集合中移到末尾去

container[index] = container[container.Length - i-1];

//将隊列對應的值移到隊列中

container[container.Length - i-1] = value;

}

//result.Sort();排序

return result;

}

這樣一來，問題得到了解決了。這種做法也可以移植到不支援泛型的版本或者語言當中。

再來一點變動

上面我們處理的都是連續的情況，假如萬一讓我們在不連續的集合中随機選擇5個不重複的，比如在某個班50個學生中随機抽取5個學生來，貌似上面的做法不行了？其實不然，依然可以沿用這種思路，比如使用上面的第三種辦法即GenerateNumber3()，無非就是聲明一個字元串數組，在這個字元串數組中存放全班所有同學的姓名，然後按照下标來随機取5個姓名即可（具體代碼這裡省略）。

不過對這種情況還有不同的，比如在快女和春晚中都有短信投票的環節，最後會從所有發送短信的手機号中随機抽取幾個手機号碼作為中獎号碼（為了簡化，将一号多投的情況視作一次，并且假設沒有廉租房“連号”的“公平”情況），可能有人會想到照搬上面的情況。實際上在這種情況下不适合，有可能随機數的集合相當大，這樣就不适合在記憶體中存儲了，可以考慮使用資料庫存儲然後利用資料庫的随機函數，在不同的資料庫中取随機記錄的函數可能會不同。比如在MySQL中如下（假設表名為table_name)：

select * from `table_name` order by rand() limit 0,10

而在SQL Server中會是如下（假設表名為table_name)：

select top 10 * from  [table_name] order by newid()

至于在Oracle中如何随機抽取記錄，大家google一下吧。

當然，這個情況還可以再複雜一下，可能電視台針對短信參與的使用者要分一二三等獎，一等獎1名，二等獎2名，三等獎3名，紀念獎50名，那麼情況就會稍微再複雜一點，不過也就是再增加一個字段而已，這個字段表示目前的号碼是否已經中過獎，每次選取号碼時隻選擇那些未曾中獎過的号碼即可。

總結

關于不重複随機數生成的問題我在七八年前就遇到過，四五年前的時候曾經做過總結，最近看到有人在讨論這個問題，于是就又重新撿起這個話題了。現在撿起這個話題的目的不是想再簡單介紹可能的幾種算法，而是從思路上去說明，并且将情況慢慢複雜化，想要說明的是程式員們（不限于.NET程式員）不要用固定的思路去解決問題，可能同樣的要求在不同的場合下會有不同的做法。明白了思路才能真正做到以不變應萬變，學會一兩個控件的用法或者多指導一兩個API并不算什麼本領，能夠在遇到以前沒有碰到過的問題時迅速簡化解決思路才是本領，另一種本領就是遇到錯誤時如何快速根據經驗定位錯誤産生原因的本領。

周公

2010-08-19