Question

字典序排列

Answer 1

详细的解析：
http://blog.csdn.net/randyjiawenjie/article/details/6313729

假设这n个数的某一个排列为 P: P1 P2 P3...Pj-1 Pj Pj+1...Pk-1 Pk Pk+1...Pn

1.从该序列的 最右端 开始向左找出第一个比与自己相邻的右边数小的数，记其下标为j，即j = max{i|Pi<Pi+1}.

2.找出Pj右边比Pj大的 最小数Pk .

3.交换Pj,Pk.此时序列变为 P’: P1 P2 P3...Pj-1 Pk Pj+1...Pk-1 Pj Pk+1...Pn

4.将Pj+1...Pn 倒转，即得到此序列的后一个序列 P”: P1 P2 P3...Pj-1 Pn...Pk+1 Pj Pk-1...Pj+1

例：

1 2 3 5 7 4 6 10 9 8为1-10的一个排列

1.从该序列的最右端开始向左找出第一个比与自己相邻的右边数小的数6，其下标为7

2.6右边比6大的最小数为8

3.交换6,8得到1 2 3 5 7 4 8 10 9 6

4.将P8-P10倒转得到：1 2 3 5 7 4 8 6 9 10即为下一个序列

实现如下：