查找n個排序元素的中間k組合的高效方法

Question

假設我有一個排序數組，N，包含n元素。現在，由於k，我需要一個高效的方法來生成中間組合的k-組合（如果所有的組合都按字典順序排序）。

實施例：

N = {a,b,c,d,e} , k = 3

1：a,b,c
2：a,b,d
3：a,b,e
4：a,c,d
5：a,c,e
6：a,d,e
7：b,c,d
8：b,c,e
9：b,d,e
10：c,d,e

我需要的算法來生成組合編號5。

---

的組合數系統上的維基百科頁面說明如何可獲得這種（以貪婪的方式）。然而，因爲n非常大，我需要找到所有的中間組合k的小於n，我需要比這更有效的東西。

我希望既然感興趣的組合總是在中間，那麼找到它就有一種直接的方法。例如，上面列表中的第一個K組合總是由N中的第一個元素給出，並且類似地最後的組合總是由最後的元素給出。有沒有這種方式來找到中間組合？

http://en.wikipedia.org/wiki/Combinatorial_number_system

Answer 1

如果你正在尋找一種方式來獲得一個獨特的組合的字典索引或等級的K-索引，那麼你的問題落在二項式係數下。二項式係數處理選擇K組中的總共具有N項的獨特組合的問題。

我已經在C＃中編寫了一個類來處理使用二項式係數的常用函數。它執行以下任務：

1. 輸出所有的在一個不錯的格式K-索引的任意N型取K到一個文件中。 K-index可以用更多的描述性字符串或字母來代替。

2. 將K索引轉換爲排序二項係數表中條目的正確詞典索引或排名。這種技術比依靠迭代的較早發佈的技術要快得多。它通過使用Pascal三角形中固有的數學屬性來實現這一點，並且與迭代該集合相比非常有效。

3. 將排序後的二項式係數表中的索引轉換爲相應的K索引。使用的技術也比以前的迭代解決方案快得多。

4. 使用Mark Dominus方法來計算二項式係數，這是不太可能溢出和更大的數字作品。

5. 該類使用.NET C＃編寫，並提供了一種通過使用通用列表來管理與問題（如果有）相關的對象的方法。這個類的構造函數接受一個名爲InitTable的布爾值，當true時將創建一個通用列表來保存要管理的對象。如果此值爲false，則不會創建表。該表不需要創建，以使用上述4種方法。提供Accessor方法來訪問表。

6. 有一個關聯的測試類，顯示如何使用該類及其方法。它已經過多次測試並且沒有已知的錯誤。

要了解關於此類和下載代碼的信息，請參見Tablizing The Binomial Coeffieicent。

下面的測試代碼將計算平均字典元素的任意N型選擇k組合：

void TestMedianMethod() 
{ 
    // This test driver tests out the GetMedianNChooseK method. 
    GetMedianNChooseK(5, 3); // 5 choose 3 case. 
    GetMedianNChooseK(10, 3); // 10 choose 3 case. 
    GetMedianNChooseK(10, 5); // 10 choose 5 case. 
} 

    private void GetMedianNChooseK(int N, int K) 
    { 
    // This method calculates the median lexicographic index and the k-indexes for that index. 
    String S; 
    // Create the bin coeff object required to get all 
    // the combos for this N choose K combination. 
    BinCoeff<int> BC = new BinCoeff<int>(N, K, false); 
    int NumCombos = BinCoeff<int>.GetBinCoeff(N, K); 
    // Calculate the median value, which in this case is the number of combos for this N 
    // choose K case divided by 2. 
    int MedianValue = NumCombos/2; 
    // The Kindexes array holds the indexes for the specified lexicographic element. 
    int[] KIndexes = new int[K]; 
    // Get the k-indexes for this combination. 
    BC.GetKIndexes(MedianValue, KIndexes); 
    StringBuilder SB = new StringBuilder(); 
    for (int Loop = 0; Loop < K; Loop++) 
    { 
     SB.Append(KIndexes[Loop].ToString()); 
     if (Loop < K - 1) 
      SB.Append(" "); 
    } 
    // Print out the information. 
    S = N.ToString() + " choose " + K.ToString() + " case:\n"; 
    S += " Number of combos = " + NumCombos.ToString() + "\n"; 
    S += " Median Value = " + MedianValue.ToString() + "\n"; 
    S += " KIndexes = " + SB.ToString() + "\n\n"; 
    Console.WriteLine(S); 
    } 

輸出：

5 choose 3 case: 
    Number of combos = 10 
    Median Value = 5 
    KIndexes = 4 2 0 


10 choose 3 case: 
    Number of combos = 120 
    Median Value = 60 
    KIndexes = 8 3 1 


10 choose 5 case: 
    Number of combos = 252 
    Median Value = 126 
    KIndexes = 9 3 2 1 0 

你應該能夠端口在相當容易該類以您選擇的語言。你可能不必爲了實現你的目標而移植類的通用部分。根據您使用的組合數量，您可能需要使用比4字節整數大的字大小。