全排列问题

题目原型：

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

解法一：（递归解法）

给定一个字符串，求出这些字符的全排列。面对这种复杂的问题，我们分解成小得问题来考虑。比如，面对一个字符串，我们把它分成两个部分：第一部分是它的第一个字符，第二部分是后面剩下的所有字符。那么我们要求字符串的全排列，可以分成两步：

1,首先求出所有可能在第一个位置出现的字符（可以把第一个字符和后面的所有的字符交换所得）。

2，确定了第一个字符以后，再对后面的所有字符进行全排列。（对剩下的字符全排列就相当于一个递归的过程，又从第一步开始处理）

代码略！

解法二：（非递归解法）

要考虑全排列的非递归实现，先来考虑如何计算字符串的下一个排列。如"1234"的下一个排列就是"1243"。只要对字符串反复求出下一个排列，全排列的也就迎刃而解了。

如何计算字符串的下一个排列了？来考虑"926520"这个字符串，我们从后向前找第一双相邻的递增字，"20"、"52"都是非递增的，"26 "即满足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），0、2都不行，5可以，将5和2交换得到"956220"，然后再将替换点后的字符串"6220"颠倒即得到"950226"。

	public String getPermutation(int n, int k)
	{
		int count = 1;
		String str = "";
		int[] num = new int[n];
		for(int i =0;i<n;i++)
		{
			num[i] = i+1;
		}
		//第一个数
		if(k==1)
		{
			for(int i = 0;i<num.length;i++)
				str+=num[i];
			return str;
		}
		boolean hasFound = true;
		int i ,j;
		
		while(hasFound)
		{
			hasFound = false;
			//从后往前找降序的相邻2数,前一个数即替换数
			for(i = num.length-1;i>0;i--)
			{
				if(num[i-1]<num[i])
				{
					hasFound = true;
					break;
				}
			}
			if(hasFound==false)
				break;
			//从后向前找比替换点大的第一个数
			for(j = num.length-1;j>i-1;j--)
			{
				//替换
				if(num[j]>num[i-1])
				{
					int temp = num[i-1];
					num[i-1] = num[j];
					num[j] = temp;
					break;
				}
			}
			count++;
			//倒置i-1后面的数，//替换点后的数全部反转
			for(j=num.length-1;i<num.length-1&&j>i;i++,j--)
			{
				int temp = num[i];
				num[i] = num[j];
				num[j] = temp;
			}
			if(count==k)
				break;
		}
		//化为字符串
		for(i = 0;i<num.length;i++)
			str+=num[i];
		return str;
	}

全排列问题

原文：http://blog.csdn.net/cow__sky/article/details/19919597