65.9K
CodeProject 正在变化。 阅读更多。
Home

C++ 中的组合

Shao Voon Wong
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.55/5 (48投票s)

2016年4月12日

CPOL

10分钟阅读

viewsIcon

371985

downloadIcon

6292

一篇关于查找组合的文章。

目录

引言

组合是从一个更大的集合中挑选一个不同的唯一子集，而不考虑元素（在子集中）的顺序（位置）的方式。本文教您如何找到组合。首先，我将向您展示查找组合的技巧。接下来，我将解释如何使用我的源代码。源代码包括一个递归模板版本和一个非递归模板版本。在文章的最后，我将向您展示如何使用 next_combination() 和 next_permutation() 从更大的集合中查找较小子集的排列。

在此之前，让我先向您介绍查找组合的技巧。

技巧

本文使用的符号

  • n: n 是从中挑选 r 序列的较大序列。
  • r: r 是从 n 序列中挑选的较小序列。
  • c: c 是从 n 个不同对象中挑选 r 个对象的可能组合总数的公式：n! / (r! (n-r)!)。
  • ! 后缀表示阶乘。

解释

让我用一个非常简单的例子来解释：从 6 个字母 {A, B, C, D, E, F} 的集合中查找所有 2 个字母的组合。第一个组合是 AB，最后一个是 EF。

可能的组合总数为：n!/(r!(n-r)!)=6!/(2!(6-2)!)=15 个组合。

让我先向您展示所有组合

AB
AC
AD
AE
AF
BC
BD
BE
BF
CD
CE
CF
DE
DF
EF

如果您找不到规律，请看这里

AB | AB
A  | AC
A  | AD
A  | AE
A  | AF
---|----
BC | BC
B  | BD
B  | BE
B  | BF
---|----
CD | CD
C  | CE
C  | CF
---|----
DE | DE
D  | DF
---|----
EF | EF

任何数量字母的组合也是如此。我再给您举几个例子，然后您可以自己找出它们。

从 {A, B, C, D, E}（一个 5 个字母的集合）中组合 3 个字母。

可能的组合总数为：10

A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E

从 {A, B, C, D, E, F}（一个 6 个字母的集合）中组合 4 个字母。

可能的组合总数为：15。

A B C D
A B C E
A B C F
A B D E
A B D F
A B E F
A C D E
A C D F
A C E F
A D E F
B C D E
B C D F
B C E F
B D E F
C D E F

我想您现在应该已经注意到一个字母出现的次数了。一个字母在所有可能的组合中出现的次数的公式是 n!/(r!(n-r)!) * r / n == c * r / n。以上面的例子为例，它将是 15 * 4 / 6 = 10 次。所有字母 {A, B, C, D, E, F} 都出现了 10 次，如所示。您可以自己数一下来证明。

源代码部分

请注意，所有组合函数现在都包含在 stdcomb 命名空间中。

递归方式

我制作了一个递归函数 char_combination()，顾名思义，它接受字符数组并处理它们。使用 char_combination() 的源代码和示例在 char_comb_ex.cpp 中。我将不再提及该函数。现在，我们的重点是 recursive_combination()，这是一个模板函数，我是以 char_combination() 为指导编写的。

该函数在 combination.h 中定义如下

// Recursive template function
template <class RanIt, class Func>
void recursive_combination(RanIt nbegin, RanIt nend, int n_column,
    RanIt rbegin, RanIt rend, int r_column,int loop, Func func)
{
  int r_size=rend-rbegin;

  int localloop=loop;
  int local_n_column=n_column;

  //A different combination is out
  if(r_column>(r_size-1))
  {
    func(rbegin,rend);
    return;
  }
  //===========================

  for(int i=0;i<=loop;++i)
  {
    RanIt it1=rbegin;
    for(int cnt=0;cnt<r_column;++cnt)
    {
      ++it1;
    } 
    RanIt it2=nbegin;
    for(int cnt2=0;cnt2<n_column+i;++cnt2)
    {
      ++it2;
    } 

    *it1=*it2;

    ++local_n_column;

    recursive_combination(nbegin,nend,local_n_column,
      rbegin,rend,r_column+1,localloop,func);
      
    --localloop;
  }
}

以 'n' 为前缀的参数与 n 序列相关联，而以 r 为前缀的参数与 r 序列相关。作为最终用户，您无需关心这些参数。您需要知道的是 func。func 是您定义的一个函数。如果组合函数递归地查找组合，则必须存在用户可以处理每个组合的方式。解决方案是一个函数指针，它接受两个 RanIt 类型（代表随机迭代器）的参数。您是定义此函数的人。通过这种方式，实现了封装。您无需知道 recursive_combination() 内部是如何工作的，您只需要知道它在每次有不同组合时调用 func，并且您只需要定义 func() 函数来处理组合。必须注意的是，func() 不应写入传递给它的两个迭代器。

填写参数的典型方式是 n_column 和 r_column 始终为 0，loop 是 r 序列中的元素数量减去 n 序列中的元素数量，func 是指向您的函数的函数指针（nbegin 和 nend，以及 rbegin 和 rend 不言自明；它们分别是相应序列的第一个迭代器和最后一个迭代器之后的一个迭代器）。

仅供参考，递归的最大深度是 r+1。在最后一次递归（r+1 次递归）中，形成了每个新组合。

下面显示了一个使用 recursive_combination() 处理原始字符数组的示例

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

using namespace std;
using namespace stdcomb;

void display(char* begin,char* end)
{
  cout<<begin<<endl;
}

int main()
{
  char ca[]="123456";
  char cb[]="1234";
   
  recursive_combination(ca,ca+6,0,
                  cb,cb+4,0,6-4,display);
  cout<<"Complete!"<<endl;
    return 0;
}

下面显示了一个使用 recursive_combination() 处理整数向量的示例

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

typedef vector<int>::iterator vii;

void display(vii begin,vii end)
{
  for (vii it=begin;it!=end;++it)
      cout<<*it;
  cout<<endl;
}

int main()
{
  vector<int> ca;
  ca.push_back (1);
  ca.push_back (2);
  ca.push_back (3);
  ca.push_back (4);
  ca.push_back (5);
  ca.push_back (6);
  vector<int> cb;
  cb.push_back (1);
  cb.push_back (2);
  cb.push_back (3);
  cb.push_back (4);
   
  recursive_combination(ca.begin (),ca.end(),0,
                  cb.begin(),cb.end(),0,6-4,display);
  cout<<"Complete!"<<endl;
    return 0;
}

非递归方式

如果您对使用递归方法有疑虑，可以选择非递归模板函数（实际上有两个）。

参数甚至比递归版本更简单。这是 combination.h 中的函数定义

template <class BidIt>

bool next_combination(BidIt n_begin, BidIt n_end,
       BidIt r_begin, BidIt r_end);
       
template <class BidIt>

bool next_combination(BidIt n_begin, BidIt n_end,
       BidIt r_begin, BidIt r_end, Prediate Equal );

以及它的反向对应版本

template <class BidIt>

bool prev_combination(BidIt n_begin, BidIt n_end,
     BidIt r_begin, BidIt r_end);
       
template <class BidIt>

bool prev_combination(BidIt n_begin, BidIt n_end,
     BidIt r_begin, BidIt r_end, , Prediate Equal );

参数 n_begin 和 n_end 是 n 序列的第一个和最后一个迭代器。而 r_begin 和 r_end 是 r 序列的迭代器。Equal 是用于比较相等的谓词。

如果您愿意，可以查阅 combination.h 中这两个函数的源代码以及 next_comb_ex.cpp 和 prev_comb_ex.cpp 中的示例。

使用 next_combination 处理原始字符数组的典型方式如下

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

using namespace std;
using namespace stdcomb;

int main()
{
  char ca[]="123456";
  char cb[]="1234";
   
  do
  {
    cout<<cb<<endl;
  }
  while(next_combination(ca,ca+6,cb,cb+4));
  cout<<"Complete!"<<endl;
  
  return 0;
}

使用 next_combination 处理整数向量的典型方式如下

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

template<class BidIt>
void display(BidIt begin,BidIt end)
{
  for (BidIt it=begin;it!=end;++it)
      cout<<*it<<" ";
  cout<<endl;
}

int main()
{
  vector<int> ca;
  ca.push_back (1);
  ca.push_back (2);
  ca.push_back (3);
  ca.push_back (4);
  ca.push_back (5);
  ca.push_back (6);
  vector<int> cb;
  cb.push_back (1);
  cb.push_back (2);
  cb.push_back (3);
  cb.push_back (4);
   
  do
  {
    display(cb.begin(),cb.end());
  }
  while(next_combination(ca.begin (),ca.end (),cb.begin (),cb.end()) );
  
  cout<<"Complete!"<<endl;
  
  return 0;
}

next_combination() 工作必须满足特定条件

  1. n 序列中的所有对象都必须是不同的。
  2. 对于 next_combination()，r 序列在第一次调用时必须初始化为 n 序列的第 r 个元素。例如，要从 n=6 {1,2,3,4,5,6} 中查找 r=4 的组合，r 序列在第一次调用之前必须初始化为 {1,2,3,4}。
  3. 至于 prev_combination()，r 序列在第一次调用时必须初始化为 n 序列的最后 r 个元素。例如，要从 n=6 {1,2,3,4,5,6} 中查找 r=4 的组合，r 序列在第一次调用之前必须初始化为 {3,4,5,6}。
  4. 在查找所有组合的过程中，n 序列必须保持不变，否则结果是错误的（有道理，对吧？）。
  5. next_combination() 和 prev_combination() 对定义了 == 运算符的数据类型进行操作。这意味着如果您想对对象序列而不是 POD（普通旧数据）序列使用 next_combination()，则实例化这些对象的类必须定义重载的 == 运算符，或者您可以使用谓词版本。

当上述条件不满足时，即使 next_combination() 和 prev_combination() 可能返回 true，结果也是不确定的。

返回值

当 next_combination() 返回 false 时，无法再找到下一个组合，并且 r 序列保持不变。prev_combination() 也是如此。

关于 next_combination() 和 prev_combination() 的一些信息

  1. n 和 r 序列不需要排序即可使用 next_combination() 或 prev_combination()。
  2. next_combination() 和 prev_combination() 不使用任何 static 变量，因此即使当前序列的组合查找尚未达到最后一个组合，也可以查找不同数据类型的另一个序列的组合。换句话说，next_combination() 和 prev_combination() 不需要重置。

这两个函数的使用示例在 next_comb_ex.cpp 和 prev_comb_ex.cpp 中。

那么我们可以用 next_combination() 做什么？

有了 next_combination() 和 STL 算法中的 next_permutation()，我们就可以找到排列了！！

从 n 序列中挑选的 r 序列的总排列数公式为：n!/(n-r)!

我们可以先调用 next_combination()，然后迭代地调用 next_permutation()；这样，我们将找到所有排列。使用它们的典型方式如下

sort(n.begin(),n.end());
do
{
   sort(r.begin(),r.end());
   //do your processing on the new combination here
   do
   {
      //do your processing on the new permutation here
   }
   while(next_permutation(r2.begin(),r2.end()))
}
while(next_combination(n.begin(),n.end(),r.begin(),r.end() ));

然而，我必须提到上述代码存在一个限制。n 和 r 序列必须按升序排序才能使其工作。这是因为 next_permutation() 在遇到降序序列时将返回 false。对于未排序序列的此问题的解决方案如下

do
{
  //do your processing on the new combination here

  for(cnt i=0;cnt<24;++cnt)
  {
    next_permutation(r2.begin(),r2.end());
    //do your processing on the new permutation here
  }
}
while(next_combination(n.begin(),n.end(),r.begin(),r.end() ));

但是，此方法要求您事先计算排列的数量。

那么如何证明它们是不同的排列？

STL 中有一个 set 容器类可以使用。set 容器中的所有对象始终按排序顺序排列，并且没有重复的对象。为了我们的目的，我们将使用此 insert() 成员函数

pair <iterator, bool> insert(const value_type& _Val);

insert() 成员函数返回一个对，其 bool 组件返回 true 如果进行了插入，如果 set 中已经包含一个其键在排序中具有等效值的元素，则返回 false，并且其迭代器组件返回插入新元素或元素已位于的地址。

proof.cpp 是为此目的而编写的，使用 STL set 容器来证明生成的排列是唯一的。您可以尝试一下，但您应该首先计算将生成的排列数。太多的排列可能需要很长时间才能完成（部分原因是 set 容器的工作方式），更糟糕的是，您可能会耗尽内存！

改进的带状态的下一次组合

为了加速 next_combination，我们可以存储已生成组合的状态，这样它就不必查找当前组合元素对应于更大的集合。一种方法是将此状态存储在类中，但这违反了 STL 算法的设计。另一种方法是在每次调用时将此状态传递给 next_combination。next_combination 和 next_combination_with_state 的声明如下，以便我们可以并排比较它们。第一个是当前的 next_combination，第二个是重载的，带有第五个参数作为相等谓词，第三个是新的 next_combination_with_state，它也有四个参数，与第一个 next_combination 相同，但最后两个参数是 BidItIt 类型，这是一个其值类型是 BidIt 迭代器的迭代器。换句话说，BidItIt 是迭代器的迭代器！通过存储 n_begin 和 n_end 本身的 BidIt 迭代器，我可以在不查找对应于 n_begin 和 n_end 的 r_begin 和 r_end 范围的情况下节省一些时间。我们可以期望性能提高 4 到 10 倍，具体取决于 n 和 r 集合的大小。

// Plain old next_combination
template <class BidIt>
inline bool next_combination(
    BidIt n_begin, 
    BidIt n_end,
    BidIt r_begin, 
    BidIt r_end);

// Plain old next_combination with equality predicate
template <class BidIt, class Prediate>
inline bool next_combination(
    BidIt n_begin, 
    BidIt n_end,
    BidIt r_begin, 
    BidIt r_end,
    Prediate Equal);

// New next_combination_with_state
// its state is stored in r_beginIT and r_endIT
// which iterators of BidIt iterators
template <class BidIt, class BidItIt>
inline bool next_combination_with_state(
    BidIt n_begin, 
    BidIt n_end,
    BidItIt r_beginIT, 
    BidItIt r_endIT);
	
// New next_combination_with_state does not have 
// version with equality predicate because it compare 
// with BidIt iterators, not elements which BidIt 
// iterator pointed to.

next_combination_with_state 没有带相等谓词的版本，因为它比较的是 BidIt 迭代器，而不是元素本身。

我重现了 next_combination 用法示例，以便我们可以与 next_combination_with_state 的示例进行比较。

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

using namespace std;
using namespace stdcomb;

// for use with next_combination examples!
template<class BidIt>
void display(BidIt begin,BidIt end)
{
  for (BidIt it=begin;it!=end;++it)
      cout<<*it<<" ";
  cout<<endl;
}

//test next_combination() with iterators
int main()
{
  vector<int> ca;
  ca.push_back (1);
  ca.push_back (2);
  ca.push_back (3);
  ca.push_back (4);
  ca.push_back (5);
  ca.push_back (6);
  vector<int> cb;
  cb.push_back (1);
  cb.push_back (2);
  cb.push_back (3);
  cb.push_back (4);
   
  do
  {
    display(cb.begin(),cb.end());
  }
  while(next_combination(ca.begin (),ca.end (),cb.begin (),cb.end()) );
  
  cout<<"Complete!"<<endl;
  
  return 0;
}

next_combination_with_state 示例如下。我们不是为较小的集合构造一个整数 vector，而是从 ca 迭代器构造 cbit，一个 vector。我们还有一个新的 display2 函数来显示结果，主要区别在于 it 迭代器被解引用两次，而不是在 display 中解引用一次。请注意，我们不能在传递给 display 之前先解引用，因为 cbit.end() 不能被解引用，因为它是一个超出最后一个有效迭代器的迭代器。之前，我尝试将 cbit.begin() 和 cbit.end() 的结果放回 cb，一个已经分配的 vector。我得到了相同的性能，又回到了原点。只有当您习惯于将结果作为迭代器的迭代器时，才使用 next_combination_with_state。由于 cbit 存储 ca 迭代器，因此在您仍然拥有 cbit 的同时，ca 必须保持活动状态，否则您会得到悬空迭代器。

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

using namespace std;
using namespace stdcomb;

template<class BidItIt>
void display2(BidItIt begin, BidItIt end)
{
    for (BidItIt it = begin; it != end; ++it)
        cout << **it << " ";
    cout << endl;
}

//test next_combination_with_state() with iterators
int main()
{
  vector<int> ca;
  ca.push_back (1);
  ca.push_back (2);
  ca.push_back (3);
  ca.push_back (4);
  ca.push_back (5);
  ca.push_back (6);
  
  vector< vector<int>::iterator > cbit;
  vector<int>::iterator it = ca.begin();
  for(; it!=ca.end()-2; ++it)
    cbit.push_back(it);

  do
  {
    display2(cbit.begin(), cbit.end());
  }
  while(next_combination_with_state(ca.begin (),ca.end (),cbit.begin (),cbit.end () ) );
  
  cout<<"Complete!"<<endl;
  
  return 0;
}

如果您有兴趣，可以继续阅读文章的第二部分：C++ 中的组合，第二部分。

历史

  • 2018 年 6 月 6 日 - 添加了改进的带状态的下一次组合部分。
  • 2009 年 9 月 14 日 - 添加了示例代码
  • 2008 年 2 月 21 日 - 在源代码中添加了向量组合的查找
  • 2006 年 11 月 26 日 - 源代码更改和错误修复
    • 所有函数都包含在 stdcomb 命名空间中
    • 解决了 prev_combination 中的一个错误，即自定义类必须定义 != 运算符，除非数据类型是 POD
    • next_combination 和 prev_combination 现在在 Visual C++ 8.0 中正常运行，无需禁用检查迭代器
    • next_combination 和 prev_combination 具有谓词版本
  • 2003 年 7 月 30 日 - 在 CodeProject 上首次发布
© . All rights reserved.