STL中的next_permutation

给定一个数组a[N],求下一个数组.

2 1 3 4

2 1 4 3

2 3 1 4

2 3 4 1

.....

在STL中就有这个函数:

1.参数是(数组的第一个元素,数组的末尾),注意这是前闭后开区间,(a,a+n)

2.返回值是bool型,表示这个数组是不是最后一个元素.

3.这个函数不仅可以实现n个互异的数的全排列,也能够生成组合数.如1 2 3 3 4 4 5 6 6这样数组的全排列.

4.第一个数组是升序排列,最后一个数组是降序排列.

    ,,,};
    do{
        re(i, )cout << a[i] << " ";
        puts("");
    } ));

那么这个函数内部是如何实现的呢?

bool next(int*a, int sz){
    ;
     && a[i] <= a[i - ])i--;
    )return false;
    ;
    ;
    while (j > i)swap(a[j--], a[i++]);
    i = pos + ;
    while (a[i] <= a[pos])i++;
    swap(a[i], a[pos]);
    return true;
}
int main(){
    ,,,};
    do{
        re(i, )cout << a[i] << " ";
        puts("");
    } ));
    ;
}

输出一共12项.

巴特西

STL中的next_permutation

最新文章

热门文章