问题描述：

若有数字集合{1，2，3}，则其全排列为123、132、213、231、321、312。现给定字符数组，求其字符的全排列。

实现如下：

//1.递归方法
//如例，其全排列可以分成
//1->{2,3}
//2->{1,3}
//3->{2,1}
//再递归求其剩余字符的全排列
//重点在于如何交换字符
class Solution 
{
public:
	void swap(char &ch1, char &ch2)//交换元素值
	{
		char tmp = ch1;
		ch1 = ch2;
		ch2 = tmp;
	}

	void fullPermutation(char *str, int beginIndex, int endIndex)
	{
		if (str == NULL) return;//防御性动作
		if (beginIndex == endIndex)//当起点下标等于终点下标时，说明已没有待排元素，输出此排列情况
		{
			for (int i = 0; i <= endIndex; ++i)
				cout << str[i] << " ";
			cout << endl;
		}
		else//否则说明还有未排元素
		{
			//j代表目前需要排列的元素
			for (int j = beginIndex; j <= endIndex; ++j)
			{
				//其和beginIndex下标的元素swap，保证它是这个排列子序列中的第一个元素
				swap(str[beginIndex], str[j]);
				//接着进行递归，此时传参beginIndex需要加1，保证起点下标后移
				fullParrangement(str, beginIndex + 1, endIndex);
				//此时须将之前交换过的值换回来，保证后序的排列顺序
				swap(str[beginIndex], str[j]);
			}
		}
	}
};

方法2中使用STL中的next_permutation()函数，具体说明参见next_permutation或参考我自己实现的my_next_permutation()。

//2.非递归方法
class Solution
{
public：
	void fullPermutation(char *str, int strlen)
	{
		if (str == NULL) return;//防御性动作
		sort(str, str + strlen);//首先将str排序
		//第一次直接输出
		do
		{
			for (int i = 0; i <= strlen; ++i)
				cout << str[i];
			cout << endl;
		} while (my_next_permutation(str, str + strlen));
		//若下一个字典序存在，则继续输出，否则结束
	}
};

//my_next_permutation()实现如下
void swap(char *ch1, char *ch2)//交换元素值
{
	char tmp = *ch1;
	*ch1 = *ch2;
	*ch2 = tmp;
}
bool my_next_permutation(char *strBegin, char *strEnd)
{
	if (strBegin == NULL || strEnd == NULL) return false;//防御性动作
	if (strEnd - strBegin <= 1 ) return false;//当元素数小于等于1个时，无须排列
	
	bool flag = false;//条件标志判断是否存在下一个字典序列，初始值为假
	char *i = strEnd - 2;//i与ii表示相邻两个元素
	char *ii = strEnd - 1;
	char *j = strEnd - 1;//j表示第一个大于i元素的元素

	for (; i >= strBegin && ii > strBegin; --i,--ii)
	{
		if (*i < *ii)//寻找第一对i小于ii的相邻元素
		{
			flag = true;
			break;
		}
	}
	if (flag)//如果没找到则表示不存在下一个字典序列，反之继续
	{
		flag = false;
		for (; j > strBegin; --j)
		{
			if (*j > *i)//从末尾开始寻找第一个大于i元素的元素
			{
				flag = true;
				break;
			}
		}
		if (flag)//如果没找到则表示不存在下一个字典序列，反之继续
		{	
			swap(i, j);将两者元素的值交换
			sort(ii, strEnd);//将ii之后的所有元素排序
		}
	}
 	return flag；
}

next_permutation实现效果：

* 啊。。码字真累。。→_→ *