3

在 C# 中，我创建了一个包含各种索引列表的列表数组。我想显示 2 种不同索引组合的 1 种组合。一个里面的2个组合不能重复。

我正在尝试编写一个有 14 名配对球员的网球锦标赛。每个玩家不得与另一位玩家配对两次。

4

1 回答 1

2

您的问题属于二项式系数的范围。二项式系数处理在总共有 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. 有一个关联的测试类，它显示了如何使用该类及其方法。它已经用 2 个案例进行了广泛的测试，并且没有已知的错误。

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

有两种不同的方式来解释您的问题。在网球比赛中，锦标赛通常安排为使用单次淘汰，每场比赛的获胜者晋级。但是，一些本地俱乐部也使用循环赛，每个球员只与其他球员比赛一次，这似乎是您正在寻找的问题。

所以，问题是 - 如何计算可以与 14 名玩家（N = 14）一起玩的独特比赛的总数，其中每个玩家只玩另一个玩家（因此 K = 2）。二项式系数计算如下：

唯一组合的总数 = N！/（K！*（N - K）！）。这 ！字符称为阶乘，表示 N * (N-1) * (N-2) ... * 1。当 K 为 2 时，二项式系数减少为：N * (N - 1) / 2。所以，N 代入 14，K 代入 2，我们发现组合的总数为 91。

以下代码将遍历每个 uniue 组合：

int N = 14;  // Total number of elements in the set.
int K = 2;  // Total number of elements in each group.
// 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);
// The Kindexes array specifies the 2 players, starting with index 0.
int[] KIndexes = new int[K];
// Loop thru all the combinations for this N choose K case.
for (int Combo = 0; Combo < NumCombos; Combo++)
{
   // Get the k-indexes for this combination.  
   BC.GetKIndexes(Loop, KIndexes);
   // KIndex[0] is the first player & Kindex[2] is the 2nd player.
   // Print out the indexes for both players.
   String S = "Player1 = Kindexes[0].ToString() + ", " +
      "Player2 = Kindexes[1].ToString();
   Console.WriteLine(S};
}

你应该能够很容易地将这个类移植到你选择的语言上。您可能不必移植类的通用部分来实现您的目标。根据您使用的组合数量，您可能需要使用比 4 字节整数更大的字长。

我还应该提到，由于这是一个课堂项目，您的老师可能不会接受上述答案，因为他可能正在寻找更多原创作品。在这种情况下，您可能需要考虑使用循环。在提交解决方案之前，您应该与他核实。

于 2012-12-19T14:05:05.797 回答