隨機排序

相信一開始接觸程式的朋友們也有做過類似的題目，可能是要做一個抽獎活動，或是大樂透的抽獎程式。

需求就是要生成若干個隨機數字出來，還記得當初我在解這個題目的時候是用比較差的方式去解決，就是使用nested loop 第一個迴圈去生成隨機數，第二個迴圈去檢查目前陣列中是否有重複的數字，一開始做出來的時候超級興奮的，這可是我想了好久才解出來的方法，那時候正在上臺灣大學資訊系統訓練班–C#班級的課程，做出來以後下堂課馬上去跟老師討論，老師給我的回饋是:不錯耶，你有想到解法、但是你這個方式的時間複雜度如果遇到更大量的數字的時候，會開始變得很慢，也就是隨著數據規模增長，效率就會越來越差(Big-O 增加) ，後來我們兩個一起試驗大概到3萬左右就可以明顯看到，碰撞的機率會很高，導致時間大幅增加的情況。

後來老師教了我用另一個方式來處理也就是我們這次會使用到的，洗牌算法Knuth-Fisher-Yates shuffle!
Now Let’s Get Ready To Rumble!!!

洗牌算法Knuth-Fisher-Yates shuffle

Fisher-Yates Shuffle 是一種高效且簡單的演算法，用於隨機打亂一個序列。

其基本思想是從後向前iterate陣列，並將當前element與一個隨機選擇的element進行交換，而做到取後不放回的效果，每個element在被選擇和交換之後，不會再被重新選擇，從而實現了真正的隨機打亂。

它的效率也是非常高效的，無論資料量多大時間複雜度都會是O(n)，可能會有人想說這樣不是直接用一個Swap方法對陣列做交換就好了嗎，乍看之下這樣好像是一個合理的方式，但一般簡單的Swap方法會出現不公正的結果。

如同上圖所見，陣列中間的index會有很高碰撞的機率，具體的詳細內容可以看Stack Overflow 創辦人 Jeff Atwood 的部落格文章The Danger of Naïveté。

有時候要解決一個問題還是要回到問題的本身，比如說我們現在如果用一般的Swap方法我們只思考到了程式編程實作的一面，但忽略了數學方面的機率問題。

實作大樂透的情境

台灣的大樂透規則是數字1 – 49 然後 取六個隨機亂數，那我們就一步一步運用 Knuth-Fisher-Yates shuffle! 來實踐吧!

首先創建一個int 的array 然後把1-49的數字放進array中。

	var lotteryArray = new int[49];

	for (int i = 0; i < lotteryArray.Length; i++)
	{
		lotteryArray[i] = i + 1;
	}
	
	lotteryArray.Dump();

程式碼很講單喔，Dump()這個方法是LINQPad才有的，是一個非常好用的方法，可以把任何物件都打印（print）出來。
用 Visual Studio 、 Visual Studio Code 可以使用 Foreach 迴圈加上 Console.WriteLine 方法
JavaScript可以使用console.log()。

阿C#這邊還有一個更簡單的方法使用Enumerable.Range這個API去生成

好的接著來寫我們的Knuth-Fisher-Yates shuffle

public void KnuthFisherYatesShuffle(int[] array)
{
	var random = new Random();
	for (int i = array.Length - 1; i > 0; i--)
	{
		var temp = array[i];
		var j = random.Next(i + 1);
		array[i] = array[j];
		array[j] = temp;
	}
}

接者我們來使用他看看情況如何

把array洗亂後再用LinQ的Take方法取前6筆出來，這樣就完成台灣大樂透的遊戲方式了。

將方法改為泛型

這邊我們還可以將我們的 KnuthFisherYatesShuffle 方法再改良一下，使他可以接受泛型的array這樣他可以做的事就更多了，像是可以隨機產生驗證碼，或是隨機的一個字符串。

public void KnuthFisherYatesShuffle<T>(T[] array)
{
	var random = new Random();
	for (int i = array.Length - 1; i > 0; i--)
	{
		var temp = array[i];
		var j = random.Next(i + 1);
		array[i] = array[j];
		array[j] = temp;
	}
}

這樣我們的方法已經很有彈性，可以接收任意型別的array了。

最後的一步關於Random的碰撞機率

在計算機科學中的隨機亂數沒辦法做到像現實生活中意義上的真正隨機，所以都是偽隨機的，Radom這個Class產生出來的隨機數，在大部分的情況下已經是可以堪用的狀況，可以參考[.NET][C#]密碼學(隨機數筆記)

如果想用更高的隨機性質量我們可以使用RandomNumberGenerator

public void KnuthFisherYatesShuffle<T>(T[] array)
{
	using (var rng = RandomNumberGenerator.Create())
	{
		byte[] randomBytes = new byte[4];

		for (int i = array.Length - 1; i > 0; i--)
		{
			rng.GetBytes(randomBytes);
			uint randomValue = BitConverter.ToUInt32(randomBytes, 0);
			int j = (int)(randomValue % (uint)(i + 1));

			var temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}
}

這是我們最終的代碼，new byte[4] 是因為int 為32位元，uint是為了確保都會是正整數的情況，做到這一步，可以說目前我們這個方法已經算是非常公正並且在機率學上是可以被接受的了!

這次的文章就到這邊，如果發現有任何疏漏，或是想與我分享的都歡迎留言~