C++ 中的组合，第二部分

Shao Voon Wong

4.81/5 (22投票s)

2016年4月12日

CPOL

15分钟阅读

108518

2375

介绍查找组合的 4 种新算法。

引言

本文介绍了 4 种新算法。第一个是关于使用整数作为数组索引的速度优化（稍后解释）。第二个是关于并发编程（随着多核 CPU 成为主流，您可以将查找大量组合的时间减半甚至更多）。第三个和第四个算法是关于查找带有重复项的组合。

在我的文章中，我非常强调尽可能清晰地解释技术。读者能够理解这些解释至关重要。因为一旦您理解了它们，您就不需要知道我怎么做；您可以自己实现，甚至可以用您喜欢的计算机语言实现。您可以自己实现，还是以迭代的方式？递归的方式？您自己的方式？天哪！您的实现甚至可能比我的更快，谁知道呢？

源代码版本

对于源代码更改，所有类和函数都归属于 stdcomb 命名空间，并被赋予“组合库”的名称以及版本号（1.5.0），以便用户知道哪个是最新版本，因为网上流传着几个源代码副本。请始终获取最新版本，因为它包含新功能和/或错误修复。您可以始终确信 CodeProject 拥有最新版本。

查找组合的另一种方法

组合是从一个较大的序列中选取一个不同的、唯一的较小子序列，而不考虑元素在（较小子序列中的）顺序（位置）。本文教您如何查找组合。对于本文中提出的每种技术，我都会尽我所能地进行解释，然后再教您如何使用源代码。

本文使用的符号

n ：n 是从中选取 r 个序列的较大序列

r ：r 是从 n 序列中选取的较小子序列。

c ：c 是从 n 个不同对象中选取 r 个的可能组合总数的公式：n! / (r! (n-r)! )

! 后缀表示阶乘。

不重复组合的查找技术

我添加此部分是因为我意识到原始文章中的解释对于读者来说不容易直观理解底层模式。现在让我解释新的方法：移位技术。

为了查找组合，我们将使用一种涉及将最后一个组合元素从左移到右的技术。

查找从序列 5 中选取 1 的组合

让我们先从数字序列 {0,1,2,3,4} 中查找选取 1 的组合。请注意，红框是组合元素。

总共生成了 5 个组合。

查找从序列 5 中选取 2 的组合

第一个例子很简单，不是吗？让我们继续从数字序列 {0,1,2,3,4} 中查找选取 2 的组合。请注意，红框是组合元素。

糟糕，我们无法再移动最后一个元素了。现在我们移动第一个元素，并将最后一个元素移回到它的右侧。如下所示。

对于接下来的 2 个组合，我们继续移动最后一个元素。

同样，我们无法再移动了，所以我们移动第一个元素，并将最后一个元素移到其旁边。

像往常一样移动最后一个元素。

移动第一个元素，并将最后一个元素移到其旁边。

糟糕，我们既不能移动第一个元素也不能移动最后一个元素了。所有的组合都已生成完毕。

总共生成了 10 个组合。

查找从序列 5 中选取 3 的组合

让我们继续从数字序列 {0,1,2,3,4} 中查找选取 3 的组合。请注意，红框是组合元素。但是对于这个，我将不进行解释。请观察模式。

总共生成了 10 个组合。

查找组合的步骤

当然，我可以继续演示从 5 个中选取 4 个元素的组合等等。但我没有。我相信您可以根据查找不同序列的组合的技术进行推断。

让我们定义我们用于查找所有组合的移位模式的步骤。

最初，所有元素都必须在数组的最左边。
移动最后一个红框，直到它不能再移动为止，然后移动右边第二个红框（如果存在），并将最后一个元素移回到其右侧。这就是新的组合。
继续将最后一个元素向右移动。
当最后 2 个元素无法再移动时，然后移动（从右边数）第 3 个元素，并将最后 2 个元素连续地移到其旁边。
上一点的重述适用于所有任意情况 - （这里的“i”表示数字）。当最后 i 个元素无法再移动时，然后移动（从右边数）第 i+1 个元素，并将最后 i 个元素连续地移到其旁边。
继续直到所有元素都不能再移动为止，所有组合都已生成。

优化版本：索引组合

有没有办法优化 next_combination() 函数使用的技术？答案是肯定的，但我们必须放弃 next_combination() 的通用性。

现在，next_combination() 将要移动的元素与 n 序列中的其他元素进行比较，以了解其在 n 序列中的当前位置。让我们看看是否可以摆脱这种查找操作。

看看这个组合（从 5 中选取 2）

01234
 x x

如果 r 序列中的 2 个元素是存储其在 n 序列中位置的整数，那么就不需要查找了。通过这种方法，返回的组合是 n 序列中索引的组合，不再是对象的组合。对于任意自定义对象的序列查找组合的时间是相同的，O(1)，因为使用了整数索引。

此方法需要定义 == 运算符才能正常工作；除非您使用了谓词版本，否则 next_combination 需要它。其他要求保持不变。总之，查找对象的组合实际上与查找整数的组合相同。整数变量应该比类对象更快，因为对象存在开销。所以我们应该使用这个！

此技术在 CIdxComb 类中实现。以下是如何使用 CIdxComb 类的示例。

#include <iostream>
#include <string>
#include <vector>
#include "IndexCombination.h"

using namespace std;
using namespace stdcomb;
void foo()
{
   CIdxComb cb;
   cb.SetSizes(5,3);
   // n sequence
   vector<string> vsAnimal;
   vsAnimal.push_back( "Elephant" );
   vsAnimal.push_back( "Deer" );
   vsAnimal.push_back( "Cat" );
   vsAnimal.push_back( "Bear" );
   vsAnimal.push_back( "Ape" );
   // r sequence
   vector<unsigned int> vi(3);
   vi[0] = 0;
   vi[1] = 1;
   vi[2] = 2;

   cout<< vsAnimal[ vi[0] ] << " " 
      << vsAnimal[ vi[1] ] << " " 
      << vsAnimal[ vi[2] ] << "\n";

   int Total = 1;
   while ( cb.GetNextComb( vi ) )
   {
      // Do whatever processing you want
      // ...

      cout<< vsAnimal[ vi[0] ] << " " 
         << vsAnimal[ vi[1] ] << " " 
         << vsAnimal[ vi[2] ] << endl; 

      ++Total;
   }

   cout<< "\nTotal : " << Total << endl;
}

next_combination() 和 CIdxComb 之间的基准测试

下面是 next_combination() 和 CIdxComb 在查找从 45 个元素中选取 6 个元素的组合时的基准测试结果，重复 10 次，使用 QueryPerformanceCounter()，在 Intel P4 2.66Ghz CPU 和 1GB DDR2 RAM PC 上运行。

next_combination - 1925.76 毫秒
CIdxComb - 149.608 毫秒

此基准测试程序包含在源代码中！

在某些调试版本中，CIdxComb 的运行速度与 next_combination 一样慢甚至更慢，这是一个非常奇怪的现象。我不知道为什么。但我认为这种差异是由于 std::vector 中迭代器（next_combination() 使用）和数组下标索引（CIdxComb 使用）的处理方式不同。上述结果来自未进行任何优化的发布版本。

并发辅助算法

让我们考虑一种情况，您需要生成大量的组合，比如 1000 亿。您有一个双核 CPU PC，所以您自然希望通过并发处理（多线程）来最大化双核的利用率。您可以做到，如果您能告诉第一个线程计算从第一个组合开始的组合，而第二个线程从第 500 亿个组合数开始。每个线程将找到 500 亿个组合。

问题是您不知道第 500 亿个组合是什么！假设您没有双核 CPU PC 或 SMP PC，您有 4 台计算机，那么如何处理呢：您可以告诉第一台计算机计算从第 1 个到第 250 亿个，第二台计算机计算从第 250 亿零 1 个到第 500 亿个，依此类推。缺失的环节是根据组合总数中的位置来计算组合的方法，以便 CIdxComb 或 next_combination() 可以继续从那个组合开始查找。

幸运的是，您的英雄，也就是我，已经找到了一种方法。解释此方法的最简单方法是跟我一起通过一个简单的例子。

给定索引查找组合的技术

让我们找出从序列 10 中选取 3 的第 92 个组合。请注意，在零基计数中，这将是第 91 个。总共有 120 个组合。

下面是并排显示的组合位置。我稍后将向您展示我如何推导出这些位置，所以现在您就接受它们是正确的。第一个元素用红框表示，第二个用绿框表示，第三个用蓝框表示。

让我们先找到红框的位置。

第 0 位

第 36 位

第 64 位

第 85 位

第 100 位

第 110 位

第 116 位

第 119 位

由于我们要找的是第 91 位，它介于第 85 位和第 100 位之间，所以第 91 个组合的第一个元素是 3。

要找到第二个元素（绿框），我们必须从 91 中减去 85，结果是第 6 个组合。

第 0 位

第 5 位

第 9 位

第 12 位

第 14 位

由于第 6 位介于第 5 位和第 9 位之间，第二个元素是 5。

在找到第三个元素之前，我们必须从 6 中减去 5，结果是第 1 个组合。

第 0 位

第 1 位

第 2 位

第 3 位

从上面的第 1 个组合，我们可以看到第三个元素是 7。

现在已经找到了所有 3 个元素，我们得到了下面的第 91 个组合

第 91 位

让我们回到如何知道位置的问题，给定一个元素并排的组合。

第 0 位

第 36 位

上面第二个组合为什么是第 36 位？看看下面

第 0 位

第 36 位

这个组合是第 36 位，因为从 9 个元素中选取 2 个的组合总数为 36。由于这是零基的，下一个组合就是第 36 位。让我再举个例子！

第 36 位

第 64 位

这个组合是第 64 位，因为从 8 个元素中选取 2 个的组合总数为 28，将 28 加到 36 上，您将得到 64。

组合数（Combinadic）

组合数（Combinadic）就是我刚才描述的方法。您可能想在 Combinadic wiki 上阅读更多关于它的内容，因为您会发现我的解释和方法与那里写的不同。这是有原因的，因为我自行重新发现了这种方法，并在撰写本节时，我发现了 Combinadic。请放心，我的方法和 Combinadic 实际上是同一种方法，只是得到答案的方式不同。

这里有一个小花絮：我非常沮丧，因为我不是第一个发现这种方法的人，直到我停止写这篇文章一年。嗯，我发明这种算法的原因是找到一种方法，将查找组合的工作分成不同的工作负载，以便在多个处理器上加速工作。我发现了两种算法，Combinadic 和 Factoradic，但 Combinadic 是我最先发现的。后来，我发现该算法可以被修改以根据位置查找排列。我还发现我不是第一个发现 Factoradic 的人。

您可能已经注意到 CFindCombByIdx 只处理数字，并且第一个组合向量的内容总是从零开始并以连续数字表示。不像 next_combination()（通过比较）那样处理对象，CFindCombByIdx 处理基于零的连续数字。您将从其结果中获得索引。例如，您从 {0,1,2,3,4} 中得到 {0,2,1} 的结果，这意味着第一个元素是您最初想要查找组合（对象）数组的索引 0，第二个元素指的是数组的索引 2，第三个元素是数组的索引 1。查找数字的组合比查找对象更容易、更快。CFindCombByIdx 使用大整数类，因为该算法使用阶乘来查找组合，而阶乘通常是很大的数字。由于它是一个模板类，并且您知道所使用的阶乘不会超过 64 位，因此您可以使用 __int64 类型代替。这是上面示例代码的输出。

示例代码

   CFindCombByIdx< CFindTotalComb<BigInteger>, 
       BigInteger > findcomb;

   const unsigned int nComb = 3;
   const unsigned int nSet = 10;

   // Intialize the vector with size nComb
   vector<unsigned int> vec(nComb);

   // vector returned by FindCombByIdx is the combination at 91.
   findcomb.FindCombByIdx( nSet, nComb, 91, vec );

下面是 next_combination、CIdxComb 和 CFindCombByIdx 在查找从 20 个元素中选取 6 个元素的组合（总共 38760 个组合）时的计时结果。

time taken for next_combination: 5.04 milliseconds
time taken for CIdxComb: 0.88 milliseconds
time taken for CFindCombByIdx:  5886.43 milliseconds

如您所见，CFindCombByIdx 与其他 2 种算法相比非常慢，但我们只使用 CFindCombByIdx 来查找我们想要的第 n 个组合，并使用 CIdxComb 来查找其余连续的组合。

PC 的基准测试程序

我包含了一个名为 TimeCombinations 的演示程序，供您对 PC 进行基准测试。了解双核或四核 PC 可以减少多少时间是很有意义的。该程序不存储组合，并在每次计算后将其丢弃。如果您有单核 PC，那么此基准测试程序对您来说作用不大。下面是程序的屏幕截图。

combinations_cpp_2/timecomb.png

combinations_cpp_2/timecombresults1.png

combinations_cpp_2/timecombresults2.png

从带有重复元素的集合中查找组合

从带有重复元素的集合中查找组合与从不重复元素的集合中查找组合几乎相同：使用移位技术，并且在应用此技术之前需要对集合进行排序。只是有些特殊情况需要您注意。

让我举一个例子，查找从 {0,1,2,3,3,3,4,5} 中选取 3 的组合，数字 3 重复了 3 次。

通过此组合，绿框在第 4 列，也就是数字 3。

如果您得到下一个组合，您需要将绿框移到最后一个 3，也就是第 6 列，然后再返回此组合结果，这样下一个组合就不会重复并且是正确的。

需要注意的另一种情况如下。

如果您使用组合移位技术，下一个组合将如下所示

您需要分别将绿框和蓝框移到第 5 列和第 6 列，这样下一个组合才是正确的。

以上是查找带重复元素的集合的组合时需要了解和注意的所有事项。

从带重复元素的集合中查找组合的示例代码

下面是示例。用于查找组合的类名为 CCombFromRepSet。由于代码直接明了并附有注释，因此我将不解释代码的工作原理。

#include <vector>
#include <iostream>
#include "CombFromRepSet.h"

using namespace std;
using namespace stdcomb;

int main()
{
   // Initialize the set
   vector<unsigned int> svi;
   svi.push_back(0); // 0
   svi.push_back(1); // 1
   svi.push_back(2); // 2
   svi.push_back(3); // 3
   svi.push_back(3); // 4
   svi.push_back(3); // 5
   svi.push_back(4); // 6
   svi.push_back(5); // 7

   // Object to find the combinations from set with repeated elements
   CCombFromRepSet cfrs;
   cfrs.SetRepeatSetInfo( svi );
  
   // Set the size of Set and number elements of the combination
   const unsigned int SET = 8;
   const unsigned int COMB = 3;
   cfrs.SetSizes( SET, COMB );

   // Initialize the first combination vector
   vector<unsigned int> vi;
   for( unsigned int j=0; j<COMB; ++j )
      vi.push_back( j );

   // Set the first combination
   cfrs.SetFirstComb( vi );

   // Display the first combination
   int Cnt=0;
   {
      cout<<Cnt<<")";
      ++Cnt;
      for( unsigned int i=0; i<vi.size(); ++i)
      {
         cout<<svi[vi[i]]<<",";
      }
      cout<<endl;
   }

   // Find and display the subsequent combinations
   while( cfrs.GetNextComb( vi ) )
   {
      cout<<Cnt<<")";
      ++Cnt;
      for( unsigned int i=0; i<vi.size(); ++i)
      {
         cout<<svi[vi[i]]<<",";
      }
      cout<<endl;
   }
   
   system( "pause" );

   return 0;
}

这是示例代码的输出

0)0,1,2,
1)0,1,3,
2)0,1,4,
3)0,1,5,
4)0,2,3,
5)0,2,4,
6)0,2,5,
7)0,3,3,
8)0,3,4,
9)0,3,5,
10)0,4,5,
11)1,2,3,
12)1,2,4,
13)1,2,5,
14)1,3,3,
15)1,3,4,
16)1,3,5,
17)1,4,5,
18)2,3,3,
19)2,3,4,
20)2,3,5,
21)2,4,5,
22)3,3,3,
23)3,3,4,
24)3,3,5,
25)3,4,5,

从不重复元素的集合中查找重复组合

现在我们来到了文章的最后一个算法：从不重复元素的集合中查找重复组合！让我再次重申：组合是从一个较大的序列中选取一个不同的、唯一的较小子序列，而不考虑元素在（较小子序列中的）顺序（位置），这意味着 {0,0,1}、{0,1,0} 和 {1,0,0} 实际上是同一个组合，因为它们都包含一个 1 和两个零。

计算重复组合总数的公式：(n + r - 1)!/(r!.(n-1)!)

让我通过查找从 5 个元素 {0,1,2,3,4} 中选取 3 个的组合来解释。

0,0,0 -> the 1st combination
0,0,1
0,0,2
0,0,3
0,0,4
0,1,1 -> this combination is 0,1,1, not 0,1,0 because we already have 0,0,1. 
0,1,2
0,1,3
0,1,4
0,2,2 -> this combination is 0,2,2, not 0,2,0 because we already have 0,0,2. 
0,2,3
.
.
0,4,4
1,1,1 -> this combination is 1,1,1, not 1,0,0 because we already have 0,0,1. 
1,1,2
1,1,3
1,1,4
1,2,2 -> this combination is 1,2,2, not 1,2,0 because we already have 0,1,2.
.
.
4,4,4 -> Last combination

作为经验法则，当我们跨越到最左边列的下一个级别时（您可能已经注意到从上面的解释），最右边列的数字总是跟随跨越列。例如，下一个组合 0,4,4 是 1,1,1，第一列从 0 跨越到 1，第二列和第三列跟随第一列。让我再举一个例子，下一个组合 0,0,4 是 0,1,1，第二列从 0 跨越到 1，第三列跟随第二列。请记住，当跨越时，跨越列之后最右边列的最小数字跟随跨越列。

从重复元素集合中查找组合的示例代码

下面是示例。用于查找组合的函数名为“CombWithRep”。由于代码直接明了并附有注释，因此我将不解释代码的工作原理。

#include <iostream>
#include <vector>
#include <string>
#include "CombWithRep.h"

using namespace std;
using namespace stdcomb;

int main()
{
   const int SET = 5;
   const int COMB = 3;
   
   // Initialize the first combination vector to zeros
   std::vector<unsigned int> vi( COMB, 0 );

   // Display the first combination
   int Cnt=0;
   {
      cout<<Cnt<<")";
      ++Cnt;
      for( int j=0; j<COMB; ++j )
      {
         cout<< vi[j] << ",";
      }
      cout<<endl;
   }
   // Find and display the subsequent combinations
   while( CombWithRep( SET, COMB, vi ) )
   {
      cout<<Cnt<<")";
      for( int j=0; j<COMB; ++j )
      {
         cout<< vi[j] << ",";
      }
      cout<<endl;
      ++Cnt;
   }

   cout<<endl;

   system( "pause" );

   return 0;
}

这是示例代码的输出

0)0,0,0,
1)0,0,1,
2)0,0,2,
3)0,0,3,
4)0,0,4,
5)0,1,1,
6)0,1,2,
7)0,1,3,
8)0,1,4,
9)0,2,2,
10)0,2,3,
11)0,2,4,
12)0,3,3,
13)0,3,4,
14)0,4,4,
15)1,1,1,
16)1,1,2,
17)1,1,3,
18)1,1,4,
19)1,2,2,
20)1,2,3,
21)1,2,4,
22)1,3,3,
23)1,3,4,
24)1,4,4,
25)2,2,2,
26)2,2,3,
27)2,2,4,
28)2,3,3,
29)2,3,4,
30)2,4,4,
31)3,3,3,
32)3,3,4,
33)3,4,4,
34)4,4,4,

结论

我们已来到文章的结尾。我们已经涵盖了查找整数不重复组合的优化算法，查找给定索引（以便将工作分配给不同处理器）的不重复组合的算法，查找带重复元素的集合的组合的优化算法，最后是查找重复组合。我希望您觉得我的文章有用且易于理解。我乐于听到您的反馈，无论是好是坏，以便改进我的文章！谢谢！

参考文献

历史

2009 年 4 月 7 日 - 更新了基准测试源代码和应用程序
2009 年 3 月 12 日 - 更改了源代码以使用 Matt McCutchen 编写的 C++ 大整数库，从而无需下载和编译 Crypto++，并减小了下载大小。
2007 年 11 月 17 日 - 首次发布