文章目錄

编写一个程序,用字典顺序列出n个元素的所有排列(Permutation).

说明:
下面是一个n = 4,用字典顺序列出来的所有排列,一共为4! = 24个。
1234 2134 3124 4123
1243 2143 3142 4132
1324 2314 3214 4213
1342 2341 3241 4231
1423 2413 3412 4312
1432 2431 3421 4321

这里是一个递归的做法。看上面4! = 24个排列的第一列,它们的第一个元素都是1,第一列的最后一个是以1开头,用字典顺序排出来的最后,自然是1432.事实上,如果是n个元素的排列,以1开头的最后一个应该是1n(n-1)…432。下一列是2开头,把n(n-1)…432中最小的一个与第一个互换,也就是把倒数第一个与第一个互换,得到2n(n-1)..431,但这不是1n(n-1)…432的下一个,但是如果把后面的n - 1个元素反过来,就会得到2134…(n-1)n,是正确的顺序,于是进入第二列。

第二列的最后一个应该是2n(n-1)…431,把 n(n-1)…431中最小的与第一个互换,但因为1已经出现过了,所以把倒数第二个元素(自然是3)与第一个互换,得到3n(n-1)…421,再把后面的n - 1个元素反过来,得到3124…(n-1)n,就得到第三列的第一个。

第三列的最后一个是3n(n-1)…421, 把n(n-1)…421中最小的与第一个互换,但因为1,2已经出现过了,所以把倒数第3个元素(自然是4)与第一个互换,得到4n(n-1)…321,再将后面n - 1个反过来排,得到4123…(n - 1)n,正好是第4列的第一个元素。

于是我们可以得到一个递归的做法,从1234…n起,用一个递归的程序
1. i = n
2. 对后面n - 1个进行排列(递归的)
3. 把第i位与第1位互换
4. i减去1
5. 把后面的n - 1位反过来排
6. 回到第2步
当i到第一位时程序结束。

需要注意的一点是,排序结束后,数组元素的位置是逆置的,要保证不改变数组元素,我们需要将数组进行一个逆置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package chapter3;

import java.util.ArrayList;
import java.util.List;

public class Permutions {
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums.length == 0)
return result;
permute(nums, 0, result);
reverse(nums, 0, nums.length - 1); //after permutation, we need to reverse array
return result;
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void reverse(int[] nums, int begin, int end) {
while (begin < end) {
swap(nums, begin, end);
begin++;
end--;
}
}
public static void permute(int[] nums, int start, List<List<Integer>> result) {
if (start == nums.length - 1) {
List<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
temp.add(nums[i]);
}
result.add(temp);
return;
}
int i = nums.length;
while (i > start) {
permute(nums, start + 1, result);
swap(nums, start, i - 1);
i--;
if (i <= start)
break;
reverse(nums, start + 1, nums.length - 1);
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
List<List<Integer>> result = permute(nums);
for (List<Integer> list: result) {
for (Integer i: list) {
System.out.print(i);
}
System.out.println("");
}
for (int i = 0; i < nums.length; i++) {
System.out.print(nums[i] + " ");
}
}
}

文章目錄