学步园

转自:http://zhangjian110518.blog.163.com/blog/static/74991703200862532221516/
   这是一个求一个排序的下一个排列的函数。如果要走遍所有的排列，你必须先排序。这是这两个函数使用需要注意的地方。其函数原形为：
 
template<class BidIt>
bool next_permutation(BidIt first, BidIt last);
template<class BidIt, class Pred>
 bool next_permutation(BidIt first, BidIt last, Pred pr);
而其prev_permutation与之相反，是求一个排列的前一个排序。
下面几个题目是北大OJ上的，这里体现出了STL的优势。（但有时STL效率并不是太高的！）

http://acm.pku.edu.cn/JudgeOnline/problem?id=1731

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int main()
{
     char ch[205];
     cin >> ch;
     sort(ch, ch + strlen(ch) );
     char *first =  ch;
     char *last = ch + strlen(ch);
     do {
         cout << ch << endl;
     }while(next_permutation(first, last));
     return 0;
}

http://acm.pku.edu.cn/JudgeOnline/problem?id=1146

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
 
int main()
{
    string str;
    while(cin >> str && str[0] != '#'){
        if( next_permutation(str.begin(), str.end())){
            cout << str << endl;
        }
        else{
            cout << "No Successor" << endl;
        }
    }
    return 0;
}

http://acm.pku.edu.cn/JudgeOnline/problem?id=1256

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
 
int compare(char a, char b)
{
    if(tolower(a) == tolower(b))
       return a < b;
    else return tolower(a) < tolower(b);
}
 
int main()
{
    int len, n;
    cin >> n;
    char str[15];
    cin.ignore();
 
    while(n --) {
       cin.getline(str, 15);
       len = strlen(str);
       sort(str, str + len, compare);
       cout << str << endl;
       while(next_permutation(str, str + len, compare))
           cout << str << endl;
    }
    return 0;
}

http://acm.pku.edu.cn/JudgeOnline/problem?id=1833

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
 
int main()
{
    int nCases, n, k, i;
    int num[1024];
    scanf("%d", &nCases);
 
    while(nCases --) {
       scanf("%d%d", &n, &k);
       for(i = 0; i < n; i++)
           scanf("%d", &num[i]);
       for(i = 0; i < k; i++)
           next_permutation(num, num + n);
       for(i = 0;i < n; i++)
           printf("%d ", num[i]);
       printf("\n");
    }
 
    return 0;
}