【分治策略】全排列

---

一、题目描述

二、思路分析

若R = {1, 2, 3} 对应的全排列就是
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2

进行层次分析：

三、递归程序

#include<iostream>
using namespace std;
#if 1
void Perm(int* arr, int left, int right)
{
	if (left == right)
	{
		//确定只剩下一个元素时
		for (int i = 0; i <= right; ++i)
		{
			cout << arr[i] << " ";
		}
		cout << endl;
	}
	else
	{
		//需要确定相对首元素
		for (int i = left; i <= right; ++i)
		{
			swap(arr[left], arr[i]);
			Perm(arr, left + 1, right);
			swap(arr[left], arr[i]);
		}
	}
}

int main()
{
	int arr[] = {1 ,2 ,3};
	int len = sizeof(arr) / sizeof(arr[0]);
	Perm(arr, 0, len - 1);
	return 0;
}

#endif