全排列next_permutation()的用法

1.std::next_permutation函数原型

template <class BidirectionalIterator>

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last );

template <class BidirectionalIterator, class Compare>

bool next_permutation (BidirectionalIterator first,BidirectionalIterator last, Compare comp);

说明：next_permutation，重新排列范围内的元素[第一，最后一个）返回按照字典序排列的下一个值较大的组合。

返回值：如果有一个更高的排列，它重新排列元素，并返回true；如果这是不可能的（因为它已经在最大可能的排列），它按升序排列重新元素，并返回false。

简单用法：

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{int a[5];
for (int i = 0; i < 5; i++)
a[i] = i;
do
{
for (int i = 0; i < 5; i++)
cout<<a[i];cout<<endl;
} while (next_permutation(a, a+5));
for (int i = 0; i < 5; i++)
cout<<a[i];
cout<<endl;
return 0;

}

从后向前输出全排列01234——43210

输出：

01234
01243
01324
01342
01423
01432
02134
02143
02314
02341
02413
02431
03124
03142
03214
03241
03412
03421
04123
04132
04213
04231
04312
04321
10234
10243
10324
10342
10423
10432
12034
12043
12304
12340
12403
12430
13024
13042
13204
13240
13402
13420
14023
14032
14203
14230
14302
14320
20134
20143
20314
20341
20413
20431
21034
21043
21304
21340
21403
21430
23014
23041
23104
23140
23401
23410
24013
24031
24103
24130
24301
24310
30124
30142
30214
30241
30412
30421
31024
31042
31204
31240
31402
31420
32014
32041
32104
32140
32401
32410
34012
34021
34102
34120
34201
34210
40123
40132
40213
40231
40312
40321
41023
41032
41203
41230
41302
41320
42013
42031
42103
42130
42301
42310
43012
43021
43102
43120
43201
43210
01234

Process returned 0 (0x0)   execution time : 0.403 s
Press any key to continue.

字符串用法：

c++

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
string str;
cin >> str;
sort(str.begin(), str.end());
cout << str << endl;
while (next_permutation(str.begin(), str.end()))
{
cout << str << endl;
}
return 0;
}
其中还用到了 sort 函数和 string.begin()、string.end() ，函数声明如下：

#include <algorithm>
void sort( iterator start, iterator end );

sort函数可以使用NlogN的复杂度对参数范围内的数据进行排序。

#include <string>
iterator begin();
const_iterator begin() const;

#include <string>
iterator end();
const_iterator end() const;

string.begin()和string.end() 可以快速访问到字符串的首字符和尾字符。

c（比c++效率高
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 100

using namespace std;

int main()
{
int length;
char str[MAX];
gets(str);
length = strlen(str);
sort(str, str + length);
puts(str);
while (next_permutation(str, str + length))
{
puts(str);
}
return 0;
}

实例
蓝桥2015第3题：竖式加法
题目大意
祥 瑞 生 辉
三 羊 献 瑞
−−−−−−−−
三 羊 生 瑞 气

题目用了8个不同的汉字，表示0~9里八种不同的数字。组成两个数值相加，等于第三个数值。

题解
定义一个数组int a[10]，初始化用a[i]存储i。将a[2]~a[9]与各个汉字对应，然后用next_permutation全排列暴力解，注意三个数值开头不能为0，能解出第2个数值，即“三羊献瑞”对应的数字是1085。
/*题解
定义一个数组int a[10]，初始化用a[i]存储i。将a[2]~a[9]与各个汉字对应，然后用next_permutation全排列暴力解，注意三个数值开头不能为0，能解出第2个数值，即“三羊献瑞”对应的数字是1085。
*/
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
int a[10];
for (int i = 0; i < 10; i++)
a[i] = i;
do {
if (!a[2] || !a[6]) continue;
int x = a[2]*1000 + a[3]*100 + a[4]*10 + a[5];
int y = a[6]*1000 + a[7]*100 + a[8]*10 + a[3];
int z = a[6]*10000 + a[7]*1000 + a[4]*100 + a[3]*10 + a[9];
if (x + y == z) printf(“%d + %d = %d\n”, x, y, z);
} while (next_permutation(a, a+10));

return 0;
}