ThinkInJava中的接口与工厂

上得厅堂，下得厨房，写得代码，翻得围墙，欢迎来到睿不可挡的每日一小练！

题目：按字典顺序列出所有排列

内容：请写一个程序，用字典顺序列出n个元素的所有排列

这个问题有点小复杂，不是太好想，反正我是想了好久。

看到这个题目我先是想到的就是递归因为这个题目就是用指针对高位选择，然后将指针传给临近的低位再选择。

不过仔细研究原来没这么简单。以n=4举例当处理以1开头的排列时1234到1432，但是在排列2开头的时候不太好建立统一的递归关系。(没办法太统一的递归方法中将后面的数字选出来)，所以将第一位分类数字经行单独处理，其实第一位数字的选择也是又规律可循的。

1234  1432  

2134  2431

3124  3421

4123  4321

12345  15432

21345  25431

....

可以看出1和2换时2都在最后一位，2和3换时，3在倒数第二位。。。就是你换第i个数时，就在倒数第i-1位。

然后我们再来处理除第一位的排列即从i,1,2,3,4,..i-1,i+i,..n(假设第一位是i)到i,n,...i+1,i-1,...3,2,1。的排列

其实这里也是有规律的，就是先从后向前查找第一个顺序相邻的位置然后交换，然后对交换后面的排列逆序。（其实这就是分解了我们人类排序的步骤，只是人的智能比较快，我们感受不到）。

比如 21354 从后向前第一个顺序相邻是35交换53为21534然后对后面逆序21435就是21354的后面一个数了。

当数列中没有顺序相邻了，我们的排列就结束了。

如 4321,54321。

所以我们就可以按照这个规律来编写程序了。

#include <iostream>
using namespace std;

int set[1000];
bool signal = false;
int n;

int _tmain(int argc, _TCHAR* argv[])
{
	void changeFirst();
	cout << "请输入排列的集合的最大整数n：" << endl;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		set[i] = i + 1;
	}
	cout << "该集合的所有排列为：" << endl;
	changeFirst();
	getchar();
	getchar();
	return 0;
}

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

void reverse(int index_Start, int index_End)
{
	int length = index_End - index_Start;
	for (int i = 0; i <= length / 2; i++)
		swap(set[i + index_Start], set[length - i + index_Start]);

}

void permutationSet()
{
	for (int x = 0; x < n; x++)
		cout << set[x] << "  ";
	cout << endl;
	signal = false;
	int i, j, k;
	for (i = n - 2; i>0; i--)
	if (set[i]<set[i + 1])
	{
		j = i + 1;
		signal = true;
		break;
	}
	if (signal == false)
		return;
	for (k = n - 1; k>0; k--)
	if (set[k]>set[i])
		break;
	swap(set[i], set[k]);
	reverse(j, n - 1);
	permutationSet();
}

void changeFirst()
{
	int i = n - 1;
	while (i >= 0)
	{
		permutationSet();
		swap(set[0], set[i]);
		reverse(1, n - 1);
		i--;
	}
}

欢迎大家加入每日一小练，嘿嘿！

每天练一练，日久见功夫，加油！

            -End-

参考文献：《c语言名题精选百则》

ThinkInJava中的接口与工厂,布布扣,bubuko.com

ThinkInJava中的接口与工厂

原文：http://blog.csdn.net/aikongmeng/article/details/26960573