By

文章目錄

编写一个程序，用字典顺序列出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] + " ");
        }
    }
}

打赏作者

文章目錄