题目描述：
用交换的分治法实现前m（m<10）个自然数数的全排列。 提示：通过交换实现的全排列不是字典序的全排列。
输入格式:
输入一个数m，代表要用1-m个自然数的全排列。
输出格式:
输出前m个自然数的全排列。(每个数之间用一个空格隔开，每行结束后有一个空格。最后一行数后面有一个空行，即每输出一行后添加一个换行，不考虑是否是最后一行)
输入样例:
3
输出样例:
1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2
解题思路：
题目就是要求实现全排列（使用分治的思路），perm（）函数为全排列的模板
分治思路：
分治法求解问题分为三个步骤：
- 分解：将问题分为若干个子问题。
- 解决：递归地求解每个子问题。
- 合并：将每个子问题的解合并成为整个问题的解。
现在我们需要求具有n个元素的数组A的全排列。例如：大小为3的数组A=[a,b,c] ，其实应该是A=[‘a’,‘b’,‘c’]。下同），它的全排列为： [[a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a]] 这是一个大小为 n*n 的二维数组。
使用分治算法求解全排列的过程如下 ：
- 分解：将数组分为子数组 A[1…k-1] 和一个元素 A[k]。 (1≤k≤n)
- 解决：递归地求解每个子数组 A[1…k-1] 的全排列，直至子数组A[1…k-1]为空时结束递归。
- 合并：将上一步的结果—A[1…k-1]的全排列（一个二维数组）与元素A[k]合并，得出A[1…k]的全排列。例如： [[]] 与 a 合并得到 [[a]] [[a]] 与 b 合并得到 [[a,b], [b,a]] [[a,b],[b,a]] 与 c 合并得到 [[a,b,c],[a,c,b],[c,a,b],[b,c,a],[c,a,b],[c,b,a]]
代码：
package text2; import java.util.Scanner; public class 全排列_分治 { static int n; public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); int arr[] = new int[n+1]; for(int i=0;i<=n;i++) arr[i] = i; perm(arr, 1); } public static void perm(int arr[],int begin) {//确定了begin位置之前的 元素顺序 if(begin==arr.length) {//生成了一种全排列 for(int i=1;i<=n;i++) { System.out.print(arr[i]+" "); } System.out.println(); } for(int i=begin;i<arr.length;i++) { int t = arr[i]; arr[i] = arr[begin]; arr[begin] = t; perm(arr, begin+1); //必须回溯，保证原来数组的内容 t = arr[i]; arr[i] = arr[begin]; arr[begin] = t; } } }
