Posted on 2008-01-15 00:56
魔のkyo 阅读(611)
评论(0) 编辑 收藏 引用
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[10]={1,2,2,3,3,3,4,5,6,7};
int cnt=0;
do{
cnt++;
}while(next_permutation(a,a+10));
printf("%d\n",cnt);//输出302400
scanf("pause");
}
next_permutation的返回值如下：如果变换后序列是非减序的则返回0，否则返回1。
所以如果想用do{...}while(next_permutation(...));的方式生成一个集合的全排列，必须先做sort。
即便做了sort，从上面的例子我们也可以看出，当集合存在重复元素时，循环的次数并不是10!=3628800，302400是什么呢，恰是10!/(2!*3!)，也就是这个多重集的全排列数。可见在处理有重复元素的"集合"时，它是正确的且高效的，只要记住一定要先sort