用next_permutation()生成r-组合数，兼发现VC7的一个bug

待我称王封你为后i 2022-08-25 12:47 104阅读 0赞

C++ standard library提供了两个生成排列的algorithms：next\_permutation()与prev\_permutation()，却没有提供生成组合数的标准函数。

由于排列与组合之间有着密切的联系，我们很容易就可以从“排列”获得“组合”。从n个元素中任取r个元素的组合，有n! / (r! \* (n-r)!)个。这些组合可用多重集\{r·1, (n-r)·0\}的全排列来生成，请看示例程序：

\#include <algorithm>  
\#include <vector>  
\#include <iostream>  
using namespace std;

int main()  
\{  
  
// 从n个元素中，任取r个元素的所有组合：  
// G++\[o\] BCC5\[o\] VC7\[x\]  
  
const int n = 7;  
const int r = 4; // 0 <= r <= n  
vector<int> p, set;  
p.insert(p.end(), r, 1);  
p.insert(p.end(), n - r, 0);  
  
for ( int i = 0; i != p.size(); ++i )  
set.push\_back(i+1);  
  
int count = 0;  
do \{  
for ( int i = 0; i != p.size(); ++i )  
if(p\[i\])  
cout << set\[i\] << " ";  
count++;  
cout << "/n";  
\} while (prev\_permutation( p.begin(), p.end() ));  
  
cout << "There are " << count << " combinations in total.";  
\}

以上程序在G++ 3.2、BCC 5.5.1、VC7下编译通过，但在VC7版运行发生死循环。怀疑这是VC7的bug, 于是再用以下程序验证之：

\#include <algorithm>  
\#include <vector>  
\#include <iostream>  
\#include <iterator>

using namespace std;

int main()  
\{  
// 经VC7编译执行后，会死循环，不可思议！  
// BCC5\[o\] G++\[o\] VC7\[x\]  
vector<int> p;  
  
p.push\_back(2);  
p.push\_back(2);  
p.push\_back(1);

do \{  
copy(p.begin(), p.end(), ostream\_iterator<int>(cout, " "));  
cout << "/n";  
\} while (prev\_permutation(p.begin(), p.end()));  
\}

依旧是VC7版发生死循环，看来这真的是vc7中prev\_permutation()的一个bug。我向[http://www.dinkumware.com/][http_www.dinkumware.com]提交了一份bug report，得到的回复是：

Our documentation points out, for both prev\_permutation and  
next\_permutation that no two elements may have equivalent  
ordering.

P.J. Plauger

经查，[http://www.dinkumware.com/][http_www.dinkumware.com]的文档中确实有这样的说法。而在MSDN中，我没有找到类似的提法，恐怕只能解释为MS的文档的更新太慢了。

[http_www.dinkumware.com]: http://www.dinkumware.com/