枚举排列

生成可重集的排列

next_permutation

next_permutation 包含在头文件 algorithm 中，可以获得比当前排列大的下一个排列，没有比当前大的排列则返回 0

类似的还有 prev_permutation() ，可以获得比当前排列小的下一个排列，没有比当前小的则返回 0

所以我们还可以这样枚举所有排列：先手动构造出最小的排列，再不停调用 next_permutation 即可

生成 a[]={1,1,4,5,1,4} 所有排列的代码如下：

int main(){
    int a[]={1,1,4,5,1,4};
    sort(a,a+6);
    do{
        for(int i=0;i<6;i++)
            cout<<a[i]<<' ';
        cout<<endl;
    }while(next_permutation(a,a+6));
    return 0;
}

Note

这一方法可用于 可重集

这里的大小指 字典序 大小

常用 sort 函数生成最小排列，再调用 next_permutation

使用位向量方法枚举时，最高位为 1 较方便，所以先生成最大排列，再调用 prev_permutation

评论