posts - 206, comments - 61, trackbacks - 0, articles - 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

只有注册用户登录后才能发表评论。