1

假设我有一个由n 个元素组成的排序数组N 。现在，给定k，我需要一种高效的方法来生成中间组合的 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中的前k个元素给出，类似地，最后一个组合总是由最后k个元素给出。有没有办法找到中间组合？

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

4

1 回答 1

0

如果您正在寻找一种从词典索引或唯一组合的排名中获取 K 索引的方法，那么您的问题属于二项式系数。二项式系数处理在总共有 N 个项目的 K 组中选择唯一组合的问题。

我用 C# 编写了一个类来处理处理二项式系数的常用函数。它执行以下任务：

  1. 将任何 N 选择 K 的所有 K 索引以良好的格式输出到文件。K-indexes 可以替换为更具描述性的字符串或字母。

  2. 将 K 索引转换为正确的词典索引或排序二项式系数表中条目的等级。这种技术比依赖迭代的旧已发布技术快得多。它通过使用帕斯卡三角形中固有的数学属性来做到这一点，并且与迭代集合相比非常有效。

  3. 将已排序二项式系数表中的索引转换为相应的 K 索引。所使用的技术也比旧的迭代解决方案快得多。

  4. 使用Mark Dominus方法计算二项式系数，它不太可能溢出并且适用于更大的数字。

  5. 该类是用 .NET C# 编写的，并提供了一种通过使用通用列表来管理与问题相关的对象（如果有）的方法。此类的构造函数采用一个名为 InitTable 的 bool 值，当它为 true 时，将创建一个通用列表来保存要管理的对象。如果此值为 false，则不会创建表。无需创建表即可使用上述 4 种方法。提供了访问器方法来访问表。

  6. 有一个关联的测试类，它显示了如何使用该类及其方法。它已经通过多个案例进行了广泛的测试，并且没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

以下测试代码将计算任何 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 字节整数更大的字长。

于 2013-04-01T05:32:22.573 回答