// 当前位置元素与后面位置的元素依次替换
swap(arr, k, i);
permutation(arr, k + 1, m);
// 将位置换回来,继续做下一个排列.
swap(arr, k, i);
}
}
}
}
/**
* 递归(分治法思想)
*/
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; i < m; i++) {
// 当前位置元素与后面位置的元素依次替换
swap(arr, k, i);
permutation(arr, k + 1, m);
// 将位置换回来,继续做下一个排列.
swap(arr, k, i);
}
}
}
}
方法2、需要增加遍历次数即增加时间消耗，即每次遍历当前元素k,与要交换元素i之间判定是否有重复的元素，即从某个数起与它后面非重复出现的数交换
[java]
/**
* 递归(分治法思想)
*/
package full_permutation;
import java.util.Arrays;
/**
* @author hanhexin
*
*/
public class Full_permutation_1 {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 1, 2, 2 };
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++) {
// 当前位置元素与后面位置的元素依次替换
if (IsSwap(arr, k, i)) {
swap(arr, k, i);
permutation(arr, k + 1, m);
// 将位置换回来,继续做下一个排列.
// System.out.println("..k=" + k + " m=" + m + " i=" + i);
swap(arr, k, i);
}
}
}
}
// begin代表当前的位置，判断当前位置与目标替换位置之间是否与目标位置相同的数字，如果有相同的则跳过
public static boolean IsSwap(int[] arr, int begin, int desNum) {
for (int i = begin; i < desNum; i++) {
if (arr[i] == arr[desNum])
return false;
}
return true;
}
}
/**
* 递归(分治法思想)
*/
package full_permutation;
import java.util.Arrays;
/**
* @author hanhexin
*
*/
public class Full_permutation_1 {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 1, 2, 2 };
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++) {
// 当前位置元素与后面位置的元素依次替换
if (IsSwap(arr, k, i)) {
swap(arr, k, i);
permutation(arr, k + 1, m);
// 将位置换回来,继续做下一个排列.
// System.out.println("..k=" + k + " m=" + m + " i=" + i);
swap(arr, k, i);
}
}