引入：在分治策略中，我们递归地求解一个问题，在每层递归中应用如下三个步骤：
分解（Divide）步骤将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
解决（Conquer）步骤递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解。
合并（Combine）步骤将子问题的解组合成原问题的解。 -------P66《算法导论》
全排列：从n个不同元素中任取m(m≤n)个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。
问题：全排列的递归实现
编程思想：
用1 2 3为例，全排列结果为123，132，213，231，321，312 根据全排列的找到规律
1、将当前元素与后面位置的每个元素依此交换
2、交换后取后一个位置的元素为当前元素的位置，再执行1
3、当当前位置是最后一个元素的位置则输出
[java]
/**
* 递归(分治法思想)
*
*/
package full_permutation;
import java.util.Arrays;
/**
* @author hanhexin
*
*/
public class Full_permutation {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 1, 2, 3 };
permutation(arr, 0, arr.length);
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// k表示当前选取的数在数组中的位置下标,m是要排列的数组的长度.
public static void permutation(int[] arr, int k, int m) {
// 当前位置与数组最后一个位置重合时,此时打印排列数.
// System.out.println("k=" + k + " m=" + m);
if (k == m - 1) {
System.out.println(Arrays.toString(arr));
} else {
for (int i = k; i < m; i++) {
// 当前位置元素与后面位置的元素依次替换
swap(arr, k, i);
permutation(arr, k + 1, m);
// 将位置换回来,继续做下一个排列.
// System.out.println("..k=" + k + " m=" + m + " i=" + i);
swap(arr, k, i);
}
}
}
}
/**
* 递归(分治法思想)
*
*/
package full_permutation;
import java.util.Arrays;
/**
* @author hanhexin
*
*/
public class Full_permutation {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 1, 2, 3 };
permutation(arr, 0, arr.length);
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// k表示当前选取的数在数组中的位置下标,m是要排列的数组的长度.
public static void permutation(int[] arr, int k, int m) {
// 当前位置与数组最后一个位置重合时,此时打印排列数.
// System.out.println("k=" + k + " m=" + m);
if (k == m - 1) {
System.out.println(Arrays.toString(arr));
} else {
for (int i = k; i < m; i++) {
// 当前位置元素与后面位置的元素依次替换
swap(arr, k, i);
permutation(arr, k + 1, m);
// 将位置换回来,继续做下一个排列.
// System.out.println("..k=" + k + " m=" + m + " i=" + i);
swap(arr, k, i);
}
}
}
}
运行结果：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
注意到，此时用的数据为不重复的数据，现将数组改为 1 2 2
运行结果：
[1, 2, 2]
[1, 2, 2]
[2, 1, 2]
[2, 2, 1]
[2, 2, 1]
[2, 1, 2]
可以看到，具有重复排列
现需要解决排列重复的问题：
方法1、需要开辟内存用HashSet
[java]
/**
* 递归(分治法思想)
*/
package full_permutation;
import java.util.Arrays;
import java.util.HashSet;
/**
* @author hanhexin
*
*/
public class Full_permutation_2 {
/**
* @param args
*/
public static HashSet
public static void main(String[] args) {
int[] arr = { 1, 2, 2 };
permutation(arr, 0, arr.length);
for (String i : set) {
System.out.println(i);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// k表示当前选取的数在数组中的位置下标,m是要排列的数组的长度.
public static void permutation(int[] arr, int k, int m) {
// 当前位置与数组最后一个位置重合时,此时打印排列数.
if (k == m - 1) {
set.add(Arrays.toString(arr));
} else {
for (int i = k;