12

假设我有一组来自 的数字[0, ....., 499]。目前正在使用 C++ 顺序生成组合std::next_permutation。作为参考，我拉出的每个元组的大小是 3，所以我返回顺序结果，例如[0,1,2], [0,1,3], [0,1,4], ... [497,498,499].

现在，我想并行化它所在的代码，因此这些组合的顺序生成将不再起作用。是否有任何现有的算法可以ith从 500 个数字中计算 3 的组合？

我想确保每个线程，无论它获得的循环迭代如何，都可以根据i它正在迭代的计算一个独立的组合。因此，如果我想要i=38线程 1 中的组合，我可以在线程 2 中[1,2,5]同时计算为.i=0[0,1,2]

编辑下面的陈述是无关紧要的，我把自己搞混了

我查看了利用阶乘从左到右缩小每个单独元素的算法，但我不能将这些用作 500！肯定不适合记忆。有什么建议么？

4

3 回答 3

5

这是我的镜头：

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

考虑到在下一个数字增加之前有多少组合。但是，它仅适用于三个元素。我不能保证它是正确的。如果您将其与您的结果进行比较并提供一些反馈，那就太酷了。

于 2013-02-25T02:38:55.640 回答
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 个案例进行了广泛的测试，并且没有已知的错误。

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

以下测试代码将遍历每个唯一组合：

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 字节的 int。如果 500 选择 3 只是一个示例，并且您需要选择大于 3 的组合，那么您将不得不使用 long 或定点 int。

于 2013-02-25T02:37:07.477 回答
0

您可以将 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继续。

如果这个描述听起来很熟悉，那是因为它与增加一个以 10 为基数的数字的工作方式完全相同，只是基数更有趣，实际上基数因数字而异。你可以利用这个洞察力来实现这个想法的一个非常紧凑的版本：对于n从 0 到 500*499*498 的任何整数，你可以获得：

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 的数字，以您喜欢的任何方式将它们划分为子范围，并让每个分片计算其子范围中每个值的排列。

对于需要枚举子集的任何问题，此技巧都非常方便。

于 2013-02-25T02:25:11.440 回答