Combination c(5,3) is initially { 0 1 2 }
當組合類的構造函數進行如下調用時:Combination c = new Combination(5,3);
我在內存中獲得一個對象，它表示五個條目中一次取三個的最初的詞典排序的數學組合元素。內存中的對象可以被表示為如 Figure 4 所示。
Figure 4 內存中的對象
構造函數代碼創建最初的組合元素時是相當簡單的。兩個代表條目總數和子集大小的參數被分別存儲在數據成員 n 和 k 中。因為我處理的數值可能會很大， 所以我決定使用 C# 的 long 類型代替int 類型。如果我愿意的話，我可以用 ulong 類型（無符號 long）獲得雙倍的數值范圍。我用子集的大小 k 來為一個 long 類型的命名數組分配空間，然后用 0 到 k-1 范圍的整數填充每個數據單元。
計算組合元素的個數
現在我已經確定了如何創建一個組合對象，讓我們看看組合的三個基本操作的第二個——根據某個給定的條目總數 n 及子集大小 k 來計算組合元素的總數。舉個例子，如果你處理一次從 n＝5 條目中取 k＝3，這里有10種可能的組合元素：
{ 0, 1, 2 } { 0, 3, 4 }
{ 0, 1, 3 } { 1, 2, 3 }
{ 0, 1, 4 } { 1, 2, 4 }
{ 0, 2, 3 } { 1, 3, 4 }
{ 0, 2, 4 } { 2, 3, 4 }
我想實現一個 Choose(n,k) 函數，它返回組合元素的個數；Choose(5,3) 返回10。查找現有的Choose 實現，我驚訝地發現 Internet 上的大多數算法都很不耐用。在我向你展示我的 Choose 實現之前，讓我們簡要地審視一下 Choose 函數的標準實現。
編寫 Choose(n,k) 函數的標準方法是直接使用其定義公式。這是一個明顯的但是拙劣解決方案。這里是一個用 C# 編碼的典型 Choose(n,k) 函數 ：
// poor implementation of Choose(n,k)static int Choose(int n, int k){ int numerator = Factorial(n); int denominator = Factorial(k) * Factorial(n-k); return ( numerator / denominator );} 輔助函數 Factorial 的實現如下： static int Factorial(int m){ int ans = 1; for (int i = m; i >= 1; —i) { ans = ans * i; } return ans;}
這里的 Choose(n,k) 實現有幾個問題：最嚴重的是它會因為當 n 和 k 的值十分小時而溢出。注意這個 Choose(n,k) 首先計算 Factorial(n)， 即便 n 是一個很小的值，它也會迅速增大到一個非常大的數 ( 比如，21! 將溢出一個無符號的 64 位數)。其次 Choose(n,k) 的值由兩個階乘的乘積 來除，這也可能成為一個非常大的數，得出的結果可能非常小。關鍵是即使 Choose(n,k) 返回的結果很小，中間計算結果很容易溢出。
一個更好的 Choose(n,k) 實現使用一個不同的方法計算其答案。改版的 Choose(n,k) 使用以下不同的公式來計算：
Choose(n,k) = (n * (n-1) * (n-2) * ... * (n-k+1)) / ( 1 * 2 * ... * k)這個算法看起來很丑，但用一個例子來說明就知道，它更容易理解：
Choose(7,3) = (7 * 6 * 5) / (1 * 2 * 3)
這個算法取代了原來計算分子（一個大數），然后計算分母（一個大數），然后相除，你可以計算部分乘積法并隨意進行除法運算。對于 Choose(7,3) 例子，你 先計算 7 * 6 并除以 2，得到 21（譯注：原文為“getting 24”顯然不對，7 * 6/2＝21）(跳過此分數下面部分的第1項，因為被1除是沒有作用的)。這時用5乘以部分乘積并用3除，你可以得到答案35， 和前面的結果一樣。
這里對 Choose(n,k) 的第二次優化是由以下特性產生的：
Choose(n,k) = Choose(n, n-k).舉個例子，Choose(10,8) = Choose(10,2)。這不是一個明顯的關系，但是如果你用一些例子來試驗的話，你將看到為什么這是對的。直接計算 Choose(10,8) 之間涉及到計算七個部分乘積和七個除法，但是計算等價的 Choose(10,2) 只要求一個乘法和一個除法操作。