查找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字节整数大的字大小。