生成下一个排列 By ACReaper

生成下一个排列的算法有很多中，用递归来实现是最简单，最明了的。我下面介绍的不是按照递归了实现而是从实际问题分析，总结出的规律。

我们知道对于排列a1a2a3......an,如果aj < aj+1，那么交换aj,aj+1那么得到就是一个更大的排列，但是满足这个条件的有很多，到底因该选择哪一个

怎么判断，下一个排列的条件，这里我们贪心点，我们选择最后一个满足aj < aj+1的j，因为越向后面的交换后一定更靠近下一个排列，是吧，所以选择最后

一个刚好是，接着我们从第j+1，n位中选择大于aj最小的ak，把它和aj交换，这时从j+1位开始，依然保持着递减的次序，所以我们把它按照递增的顺序排列。

其实在我们选择j后，就一定有aj + 1> a j +2.....an，因为aj 是最后一个不满足这个等式的！这样就生成了下一个排列，我们只需把这代码运行n! - 1次，就能得到所有

排列。

#include <stdio.h>
#define MAXN 100
int A[MAXN];
int main(){
	int m;
	while(scanf("%d",&m) != EOF){//输入个数
		for(int i = 1; i <= m ;i++){
			scanf("%d",A + i);
		}
		int j = m - 1;
		while(A[j] > A[j + 1])//找最后一个j
			j--;
		int k = m;
		while(A[k] < A[j])//找比A【j】大的最小数
			k--;
		int temp = A[k];
		A[k] = A[j];
		A[j] = temp;
		int r = j + 1;
		int s = m;
		while(r < s){//排序
			int temp = A[r];
			A[r++] = A[s];
			A[s--] = temp;	
		}
		for(int i = 1; i <= m; i++){
			printf("%d ",A[i]);
		}
		printf("\n");
	}
	return 0;
} 

测试数据:

输入

6

3 6 2 5 4 1

输出

3 6 4 1 2 5

2013 04 20

By ACReaper