198-全排列问题（2）.md

系列文章目录

全排列算法（1） 全排列算法（2）

对于一个重复序列{ 1, 2, 2 }，其全排列只有三个：{ 1, 2, 2 }，{ 2, 1, 2 }，{ 2, 2, 1 }。

递归

我们依旧先用递归来求解。

/**
 *
 * author : 刘毅（Limer）
 * date   : 2017-06-02
 * mode   : C++
 */

#include <iostream>  
#include <algorithm>  

using namespace std;

bool IsEqual(int array[], int left, int right)
{
	for (int i = left; i < right; i++)
		if (array[i] == array[right])
			return true;
  
	return false;
}

void FullPermutation(int array[], int left, int right)
{
	if (left == right)
	{
		for (int i = 0; i < 3; i++)
			cout << array[i] << " ";
		cout << endl;
	}
	else
	{
		for (int i = left; i <= right; i++)
		{
			if (!IsEqual(array, left, i))
			{
				swap(array[i], array[left]);
				FullPermutation(array, left + 1, right);
				swap(array[i], array[left]);
			}
		}
	}
}

int main()
{

	int array[4] = { 1,2,2 };

	FullPermutation(array, 0, 2);

	return 0;
}

运行截图：

简单说下IsEqual()为什么那么写。

考虑重复序列1abc2xyz2，

• 交换1与第一个2，变成了2abc1xyz2，按照程序，接下来对abc1xyz2进行全排列；
• 假若1与第二个2交换，变成了2abc2xyz1，按照程序，接下来对abc2xyz1进行全排列。

那么问题来了，注意我加粗的两个地方，这两个全排列进行的都是同样的工作，必然会造成重复输出。

next_permutation

下面再来看下STL里的next_permutation和prev_permutation对重复序列的反应。

/**
 *
 * author : 刘毅（Limer）
 * date   : 2017-06-02
 * mode   : C++
 */

#include <iostream>  
#include <algorithm>  

using namespace std;

void FullPermutation(int array[])
{
	do
	{
		for (int i = 0; i < 3; i++)
			cout << array[i] << " ";
		cout << endl;
	} while (next_permutation(array, array + 3));
}

int main()
{

	int array[3] = { 1,2,2 };

	FullPermutation(array);

	return 0;
}

运行截图：

从结果来看，next_permutation的适应性更强，不管是不重复序列还是重复序列，它都可以输出正确的结果。其实这很好理解，next_permutation的本质是字典序原理，而字典序是严格的大于或者小于，没有等于。

全排列拓展

最后再引申一个网友提出的全排列问题：对于序列{ 1, 2, 3, 4 }，输出它所有长度的全排列，即： 1 2 3 4 1 2 1 3 . . . 1 2 3 4 1 2 4 3 . . . 4 3 2 1

这样的问题看起来有点复杂，其实很简单，再来回顾下{ 1, 2, 3, 4 }的字典序树。

我们只需控制递归的深度即可。

/**
 *
 * author : 刘毅（Limer）
 * date   : 2017-06-02
 * mode   : C++
 */

#include <iostream>  
#include <algorithm>  

using namespace std;

void FullPermutation(int array[], int left, int right, int len, int depth)
{
	if (depth == 0)
	{
		for (int i = 0; i < len; i++)
			cout << array[i] << " ";
		cout << endl;
	}
	else
	{
		for (int i = left; i <= right; i++)
		{
			swap(array[i], array[left]);
			FullPermutation(array, left + 1, right, len, depth - 1);
			swap(array[i], array[left]);
		}
	}
}

int main()
{

	int array[4] = { 1,2,3,4 };

	for (int i = 1; i <= 4; i++)
		FullPermutation(array, 0, 3, i, i);

	return 0;
}