我想實現一個 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) 只要求一個乘法和一個除法操作。
綜上所述，我實現的 Choose(n,k) 如 Figure 5 所示。在 Choose 函數中，我對 n 等于 k 的情況進行了快速檢查，如果為真，則返回 1。而 Choose 算法中沒有對之進行檢查，但它改進了生成特定 Combination 對象元素的方法性能。Choose 實現的剩余部分用我剛剛解釋的算法計算元素的總數。
生成所有組合元素
組合的第三個基本操作是根據給定條目個數 n 和子集大小 k 生成一個所有組合元素的清單。正如前面所示的 Choose 函數的問題一樣，Internet 上找到的 并不是最優方案。讓我們簡單看看一個典型的情況：給定 n 和 k 值，生成所有組合元素的解決方案，并且我將改進它。
文章來源于領測軟件測試網 http://www.kjueaiud.com/
