产生下一个排列数的算法

产生下一个排列数的算法2015-09-06全排序：

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。例如n=3，全排序为：123、132、213、231、312、321共6种。

字典序法：

对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是：从左到右逐个比较对应的字符大小。字符集{1,2,3}，较小的数字较先，这样按字典序生成的全排列即：123、132、213、231、312、321。

1.现在假设输入全排序中的一串数字，要求得到它在字典序全排列中对应的下一个排列数。比如：输入123输出132，输入12435输出12453。

算法思想：

1.从数列的右边向左寻找连续递增序列, 例如对于：1,3,5,4,2，其中5-3-2即为递增序列。

2.从上述序列中找一个比它前面的数（3）大的最小数（4），并将且交换这两个数。于是1,3,5,4,2->1,4,5,3,2，此时交换后的依然是递增序列。

3.新的递增序列逆序，即：1,4,5,3,2 => 1,4,2,3,5

#include <iostream>using namespace std;void swap（int * a, int * b）{int temp = *a;*a = *b;*b = temp;}//产生下一个排列数//存在则返回1//不存在返回0int next（int a[], int n）{int i,j,k;// 从右向左寻找非递减序列,例如对于序列1,3,5,4,2,将会找到数字5的位置for（k = n - 1; k > 0 && a[k - 1] >= a[k]; k--）;if（k == 0） return 0; //例:对于5,4,3,2,1的情形，他的下一个不存在，返回0//从非递减序列李寻找比它前面的一个数（3）大的最小数,即数字4for（i = n - 1; a[i] <= a[k - 1]; i--）;//交换3和4swap（&a[k - 1], &a[i]）;//将新的非递减序列逆序i = k;j = n - 1;while（i < j） swap（&a[i++], &a[j--]）;return 1;}void pnt（int a[], int n）{int i;for（i = 0; i < n; ++i） printf（"%d ", a[i]）;printf（"
"）;}int main（）{int a[] = {1,2,3,4};int size = sizeof（a） / sizeof（a[0]）;pnt（a, size）;while（next（a, size））pnt（a, size）;return 0;}