一个大集合的第n个或任意组合

Question

我有一组数字，范围从[0, ....., 499]。目前正在使用C++的std::next_permutation按顺序生成组合。参考文献，我要提取的每个元组的大小为3，因此我返回连续的结果，例如[0,1,2]，[0,1,3]，[0,1,4]，... [497,498,499]。

现在，我想并行化这段代码，所以顺序生成这些组合将不再起作用。是否存在任何现有算法来计算500个数字中3个数字的第i个组合？

我希望确保每个线程，无论其获取的循环迭代次数如何，都可以基于其正在迭代的i计算独立的组合。因此，如果我想在线程1中获取i=38的组合，则可以同时计算线程2中的i=0，如[0,1,2]。

我看过利用阶乘从左到右缩小每个元素范围的算法，但是我不能使用这些算法，因为500！无法放入内存中。有什么建议吗？

- anon_dev1234

---

展示一下阶乘的计算过程。你可能只是看错了。通常情况下，你会将一个阶乘除以另一个阶乘，这意味着可以进行简化。 - paddy

我认为我需要重新表达我的问题。这不仅仅是500个数字的排列，而是从500个可能中选择3个的组合。但是我想能够从500个“选择三”的可能性中选择任意组合。 - anon_dev1234

也许以下内容会对您有所帮助：http://code.google.com/p/strtk/source/browse/trunk/strtk.hpp#11622 - Gerdiner

@Gerdiner 如果我可以接受你的答案，我会的。那段代码更通用，并且完全按照所需工作。算法非常棒。谢谢！ - anon_dev1234

Answer 1

这是我提供的翻译：

int k = 527; //The kth combination is calculated
int N=500; //Number of Elements you have
int a=0,b=1,c=2; //a,b,c are the numbers you get out

while(k >= (N-a-1)*(N-a-2)/2){
    k -= (N-a-1)*(N-a-2)/2;
    a++;
}
b= a+1;
while(k >= N-1-b){
    k -= N-1-b;
    b++;
}

c = b+1+k;


cout << "["<<a<<","<<b<<","<<c<<"]"<<endl; //The result

我想到了下一个数字增加需要多少种组合方式。然而，这种方法只适用于三个元素。我不能保证它是正确的。如果您能将它与您的结果进行比较并提供一些反馈，那就太棒了。

- Haatschii

---

简单、快速，就我所知道的来看还是有效的。我一直在尝试想出类似于jacobm所写的东西，但我确实喜欢这个！ - anon_dev1234

Answer 2

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

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

将任何N选K的所有K指数以漂亮的格式输出到文件中。可以用更具描述性的字符串或字母替换K指数。 将K指数转换为排序二项式系数表中条目的正确词典序索引或排名。这种技术比依赖迭代的旧技术快得多。它通过使用帕斯卡三角形固有的数学特性来实现，与迭代集合相比非常高效。 将排序二项式系数表中的索引转换为相应的K指数。我认为这也比旧的迭代解决方案更快。 使用Mark Dominus方法计算二项式系数，这样不太可能溢出，并且适用于更大的数字。 该类是用.NET C#编写的，并提供了一种使用通用列表来管理与问题相关的对象（如果有）的方法。该类的构造函数接受一个名为InitTable的布尔值，当为true时，将创建一个通用列表来保存要管理的对象。如果此值为false，则不会创建该表。不需要创建表格即可使用上述4种方法。提供访问器方法以访问表格。 有一个相关的测试类，显示如何使用该类及其方法。它已经经过了2个案例的广泛测试，没有已知的错误。

阅读有关此类的信息并下载代码，请参见将二项式系数制表。

以下经过测试的代码将迭代每个唯一的组合：

public void Test10Choose5()
{
   String S;
   int Loop;
   int N = 500;  // Total number of elements in the set.
   int K = 3;  // 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 indexes for a lexigraphic element.
   int[] KIndexes = new int[K];
   StringBuilder SB = new StringBuilder();
   // 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(Combo, KIndexes);
      // Verify that the Kindexes returned can be used to retrive the
      // rank or lexigraphic order of the KIndexes in the table.
      int Val = BC.GetIndex(true, KIndexes);
      if (Val != Combo)
      {
         S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
         Console.WriteLine(S);
      }
      SB.Remove(0, SB.Length);
      for (Loop = 0; Loop < K; Loop++)
      {
         SB.Append(KIndexes[Loop].ToString());
         if (Loop < K - 1)
            SB.Append(" ");
      }
      S = "KIndexes = " + SB.ToString();
      Console.WriteLine(S);
   }
}

你应该能够很容易地将这个类移植到C++。你可能不需要移植类的通用部分来实现你的目标。你的测试案例中，500选3产生了20,708,500个唯一的组合，可以放在一个4字节的整数中。如果500选3只是一个示例案例，而你需要选择大于3的组合，则必须使用long或者固定点整数。

- Bob Bryan

---

我一定会研究这个。对于我们所关注的参数，500选3保证是最坏情况，因此我不太担心溢出问题。 - anon_dev1234

我将@Bob Bryan的代码移植到了Java。您可以在https://github.com/aalhossary/BinomialCoefficient找到它。 - Amr ALHOSSARY

Answer 3

你可以将500个对象中的任意3个描述为三元组(i, j, k)，其中i是从0到499的数字（第一个数字的索引），j范围从0到498（第二个数字的索引，跳过第一个数字），k范围从0到497（最后一个数字的索引，跳过前两个已选择的数字）。有了这个，枚举所有可能的选择实际上相当容易：从(0,0,0)开始，递增k直到它达到其最大值，然后递增j并将k重置为0，以此类推，直到j达到其最大值，以此类推，直到j达到自己的最大值；然后递增i并重置j和k并继续。

如果这个描述听起来很熟悉，那是因为它与增加十进制数字的方式完全相同，只不过基数更奇特，实际上基数从一位到另一位是不同的。您可以利用这个见解来实现一个非常紧凑的版本：对于任何介于0到500*499*498之间的整数n，您可以得到：

struct {
  int i, j, k;
} triple;

triple AsTriple(int n) {
  triple result;
  result.k = n % 498;
  n = n / 498;
  result.j = n % 499;
  n = n / 499;
  result.i = n % 500;  // unnecessary, any legal n will already be between 0 and 499
  return result;
}

void PrintSelections(triple t) {
  int i, j, k;
  i = t.i;
  j = t.j + (i <= j ? 1 : 0);
  k = t.k + (i <= k ? 1 : 0) + (j <= k ? 1 : 0);
  std::cout << "[" << i << "," << j << "," << k << "]" << std::endl;
}

void PrintRange(int start, int end) {
  for (int i = start; i < end; ++i) {
    PrintSelections(AsTriple(i));
  }
}

现在来谈论分片，你可以将从0到500*499*498的数字取出，以任何你喜欢的方式将它们划分为子范围，并让每个分片计算其子范围内每个值的排列。

这个技巧对于需要枚举子集的任何问题都非常有用。

- jacobm

---

这里唯一的问题是我最终会得到重复。我需要500个选择3个组合（最坏情况），即约2000万个组合。这些组合没有重复，因此(0,0,0)被排除在外。不过还是谢谢你的回答！ - anon_dev1234

不，按照我描述的方式没有重复。关键在于解释：(0,0,0) 表示第一个、第二个和第三个元素，因为对于每个数字，您都会跳过已选择的所有元素。 - jacobm

啊哈，我明白了。我会测试一下的！ - anon_dev1234

FYI，已更新上面的代码示例，使其更完整，并希望能够澄清数字解释的方式。 - jacobm

这个答案是不正确的。通过调用PrintRange(0,1)可以轻松看出来。它打印出了[0,1,1]，这甚至不是一个有效的组合。它还会产生很多重复的结果。例如，它将1映射到[0,1,2]，将498映射到[0,2,1]。要正确解决这个问题需要进行更复杂的计算。 - peastman

我刚在我的机器上尝试了PrintRange(0,1)，并按预期打印出[0,1,2]；你确定你正确复制了代码吗？关于重复项：从描述中，我认为原帖作者正在寻找所有排列（即来自1-500的3个不同数字的所有不同序列），而这段代码确实可以做到。如果是大小为3的所有子集，则此算法将无法工作。 - jacobm