1. package javabasicgrammar;
   
2. 整理了一些关于用递归算法对数组进行全排列，希望对你们有用。
   
3. import java.util.ArrayList;
   
4. import java.util.Arrays;
   
5. import java.util.List;
   
6. 
   
7. // 1.================================================================
   
8. // 排列组合数字
   
9. public class Permutation {
   
10.     // 方法一
    
11.     public static void perm(char[] buf, int start, int end) {
    
12.         if (start == end) {// 当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可
    
13.             for (int i = 0; i <= end; i++) {
    
14.                 System.out.print(buf[i]);
    
15.             }
    
16.             System.out.println();
    
17.         } else {// 多个字母全排列
    
18.             for (int i = start; i <= end; i++) {
    
19.                 char temp = buf[start];// 交换数组第一个元素与后续的元素
    
20.                 buf[start] = buf[i];
    
21.                 buf[i] = temp;
    
22. 
    
23.                 perm(buf, start + 1, end);// 后续元素递归全排列
    
24. 
    
25.                 // temp = buf[start];// 将交换后的数组还原
    
26.                 // buf[start] = buf[i];
    
27.                 // buf[i] = temp;
    
28.                 buf[i] = buf[start]; // 将交换后的数组还原
    
29.                 buf[start] = temp;
    
30.             }
    
31.         }
    
32.     }
    
33. 
    
34.     // 方法二
    
35.     // 可以使用递回将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为
    
36.     // 1 [2 3 4],2[1 3 4],3[1 2 4],4[1 2 3]进行排列，利用旋转法，先将旋转间隔设为0，
    
37.     // 将最右边的数字旋转至最左边，并逐步增加旋转的间隔，例如
    
38.     // 1 2 3 4 --> 旋转1 --> 继续将右边2 3 4进行递回处理
    
39.     // 2 1 3 4 --> 旋转1 2 变为 2 1 --> 继续将右边1 3 4 进行递回处理
    
40.     // 3 1 2 4 --> 旋转1 2 3变为3 1 2 --> 继续将右边1 2 4进行递回处理
    
41.     // 4 1 2 3 --> 旋转1 2 3 4 变为4 1 2 3 --> 继续将右边1 2 3 进行递回处理
    
42.     public static void perm(int[] num, int i) { // i为第几层
    
43.         if (i < num.length) { // 小于总层就旋转,旋转间隔从0开始
    
44.             for (int j = i; j < num.length; j++) {
    
45.                 int tmp = num[j];
    
46.                 // 旋转该区段最右边的数字到最左边
    
47.                 for (int k = j; k > i; k--) {
    
48.                     num[k] = num[k - 1];
    
49.                 }
    
50.                 num[i] = tmp;
    
51. 
    
52.                 perm(num, i + 1);
    
53. 
    
54.                 // 还原
    
55.                 for (int k = i; k < j; k++) {
    
56.                     num[k] = num[k + 1];
    
57.                 }
    
58.                 num[j] = tmp;
    
59.             }
    
60.         } else { // 最后一层的时候打印
    
61.             // 显示此次排序
    
62.             for (int j = 0; j < num.length; j++) {
    
63.                 System.out.print(num[j] + " ");
    
64.             }
    
65.             System.out.println();
    
66.         }
    
67.     }
    
68. 
    
69.     // 方法三
    
70.     private static void sort(List datas, List target) {
    
71.         if (target.size() == 3) { // 这个3表示要对几个字符进行全排列
    
72.             for (Object obj : target)
    
73.                 System.out.print(obj);
    
74.             System.out.println();
    
75.             return;
    
76.         }
    
77.         for (int i = 0; i < datas.size(); i++) {
    
78.             List newDatas = new ArrayList(datas);
    
79.             List newTarget = new ArrayList(target);
    
80.             newTarget.add(newDatas.get(i));
    
81.             newDatas.remove(i);
    
82.             sort(newDatas, newTarget);
    
83.         }
    
84.     }
    
85. 
    
86.     public static void main(String[] args) {
    
87.         // ==========================================
    
88.         // int[] num = new int[4 + 1];
    
89.         // for (int j = 1; j <= num.length - 1; j++) {
    
90.         // num[j] = j;
    
91.         // }
    
92.         // perm(num, 1);
    
93.         int[] num = { 1, 2, 3 };
    
94.         perm(num, 0);
    
95.         // ==========================================
    
96.         System.out.println();
    
97.         char buf[] = { 'a', 'b', 'c' };
    
98.         perm(buf, 0, buf.length - 1);
    
99.         // ==========================================
    
100.         System.out.println();
     
101.         String[] datas = new String[] { "a", "b", "c" };
     
102.         sort(Arrays.asList(datas), new ArrayList());
     
103.     }
     
104. }

复制代码

1. package javabasicgrammar;
   
2. 整理了一些关于用递归算法对数组进行全排列，希望对你们有用。
   
3. import java.util.ArrayList;
   
4. import java.util.Arrays;
   
5. import java.util.List;
   
6. 
   
7. // 1.================================================================
   
8. // 排列组合数字
   
9. public class Permutation {
   
10.     // 方法一
    
11.     public static void perm(char[] buf, int start, int end) {
    
12.         if (start == end) {// 当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可
    
13.             for (int i = 0; i <= end; i++) {
    
14.                 System.out.print(buf[i]);
    
15.             }
    
16.             System.out.println();
    
17.         } else {// 多个字母全排列
    
18.             for (int i = start; i <= end; i++) {
    
19.                 char temp = buf[start];// 交换数组第一个元素与后续的元素
    
20.                 buf[start] = buf[i];
    
21.                 buf[i] = temp;
    
22. 
    
23.                 perm(buf, start + 1, end);// 后续元素递归全排列
    
24. 
    
25.                 // temp = buf[start];// 将交换后的数组还原
    
26.                 // buf[start] = buf[i];
    
27.                 // buf[i] = temp;
    
28.                 buf[i] = buf[start]; // 将交换后的数组还原
    
29.                 buf[start] = temp;
    
30.             }
    
31.         }
    
32.     }
    
33. 
    
34.     // 方法二
    
35.     // 可以使用递回将问题切割为较小的单元进行排列组合，例如1 2 3 4的排列可以分为
    
36.     // 1 [2 3 4],2[1 3 4],3[1 2 4],4[1 2 3]进行排列，利用旋转法，先将旋转间隔设为0，
    
37.     // 将最右边的数字旋转至最左边，并逐步增加旋转的间隔，例如
    
38.     // 1 2 3 4 --> 旋转1 --> 继续将右边2 3 4进行递回处理
    
39.     // 2 1 3 4 --> 旋转1 2 变为 2 1 --> 继续将右边1 3 4 进行递回处理
    
40.     // 3 1 2 4 --> 旋转1 2 3变为3 1 2 --> 继续将右边1 2 4进行递回处理
    
41.     // 4 1 2 3 --> 旋转1 2 3 4 变为4 1 2 3 --> 继续将右边1 2 3 进行递回处理
    
42.     public static void perm(int[] num, int i) { // i为第几层
    
43.         if (i < num.length) { // 小于总层就旋转,旋转间隔从0开始
    
44.             for (int j = i; j < num.length; j++) {
    
45.                 int tmp = num[j];
    
46.                 // 旋转该区段最右边的数字到最左边
    
47.                 for (int k = j; k > i; k--) {
    
48.                     num[k] = num[k - 1];
    
49.                 }
    
50.                 num[i] = tmp;
    
51. 
    
52.                 perm(num, i + 1);
    
53. 
    
54.                 // 还原
    
55.                 for (int k = i; k < j; k++) {
    
56.                     num[k] = num[k + 1];
    
57.                 }
    
58.                 num[j] = tmp;
    
59.             }
    
60.         } else { // 最后一层的时候打印
    
61.             // 显示此次排序
    
62.             for (int j = 0; j < num.length; j++) {
    
63.                 System.out.print(num[j] + " ");
    
64.             }
    
65.             System.out.println();
    
66.         }
    
67.     }
    
68. 
    
69.     // 方法三
    
70.     private static void sort(List datas, List target) {
    
71.         if (target.size() == 3) { // 这个3表示要对几个字符进行全排列
    
72.             for (Object obj : target)
    
73.                 System.out.print(obj);
    
74.             System.out.println();
    
75.             return;
    
76.         }
    
77.         for (int i = 0; i < datas.size(); i++) {
    
78.             List newDatas = new ArrayList(datas);
    
79.             List newTarget = new ArrayList(target);
    
80.             newTarget.add(newDatas.get(i));
    
81.             newDatas.remove(i);
    
82.             sort(newDatas, newTarget);
    
83.         }
    
84.     }
    
85. 
    
86.     public static void main(String[] args) {
    
87.         // ==========================================
    
88.         // int[] num = new int[4 + 1];
    
89.         // for (int j = 1; j <= num.length - 1; j++) {
    
90.         // num[j] = j;
    
91.         // }
    
92.         // perm(num, 1);
    
93.         int[] num = { 1, 2, 3 };
    
94.         perm(num, 0);
    
95.         // ==========================================
    
96.         System.out.println();
    
97.         char buf[] = { 'a', 'b', 'c' };
    
98.         perm(buf, 0, buf.length - 1);
    
99.         // ==========================================
    
100.         System.out.println();
     
101.         String[] datas = new String[] { "a", "b", "c" };
     
102.         sort(Arrays.asList(datas), new ArrayList());
     
103.     }
     
104. }

复制代码