c++ STL 全排列

在c++的STL中有函数可以直接对数组元素进行全排列，即next_permutation和pre_permutation，这两个函数都可以实现全排列，只是排列的顺序不同，next_permutation作用为向后排序，而pre_permutation作用为向前排序。

需要头文件#include <algorithm>

示例

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

int main() {
    int nums[10];
    for( int i = 0; i < 10; i++ ) {
        nums[i] = i + 1;
    }

    int n;
    cin >> n;
    do {
        for( int i = 0; i < n; i++ ) {
            cout << nums[i];
        }
        cout << endl;
    } while( next_permutation( nums, nums+n ) );

    return 0;
}

运行结果:

若改为pre_permutation:

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

int main() {
    int nums[3] = {3, 2, 1};

    do {
        for( int i = 0; i < 3; i++ ) {
            cout << nums[i];
        }
        cout << endl;
    } while( prev_permutation( nums, nums+3 ) );

    return 0;
}

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

int main() {
    int nums[3] = {1, 2, 3}; //注意数据顺序的差异

    do {
        for( int i = 0; i < 3; i++ ) {
            cout << nums[i];
        }
        cout << endl;
    } while( prev_permutation( nums, nums+3 ) );

    return 0;
}

可见两者的差别为排列顺序不同。

练习

题目链接: http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=366

代码:

#include <iostream>
#include <algorithm>
#include <string>
#include <set>
using namespace std;

int main() {
    int nums[10];
    for( int i = 0; i < 10; i++ ) {
        nums[i] = i + 1;
    }

    int t, n;
    cin >> t;
    while( t-- ) {
        cin >> n;
        do {
            for( int i = 0; i < n; i++ ) {
                cout << nums[i];
            }
            cout << endl;
        } while( next_permutation( nums, nums+n ) );
    }

    return 0;
}