Java 全排列

参考：https://blog.csdn.net/joylnwang/article/details/7064115

回溯

• 描述

和高中的排列组合有些像，比如{1,2,3}有几种排列方式：
第一个位置有3种，第二个位置有2种，第三个位置有1种，也就是3 * 2 * 1=6种
只不过上面的元素是从集合中拿出的，这里的元素是数组通过和后面的元素交换得到的

• 代码

• 这个程序只会递归到倒数第二层，最后一层无需固定（图中的红线是达不到的）
• 为什么i=n？如果i和n相等那还交换什么？
  交换是为了遍历每一种情况，这个数组本身的顺序也算一种情况，这次的遍历是为了进入递归（也就是代码中的out）
• 为什么要swap两次？
  第二次swap是为了让数组保持原样，利于回溯。

    public static void out(int[] ar,int n){
        if(n==ar.length-1) {
//            输出
            print(ar);
        }
//        n代表第一个未被固定的位，i代表和n交换的数
        for (int i = n; i < ar.length; i++) {
            swap(ar,n,i);
            out(ar,n+1);
            swap(ar,n,i);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

辅助函数

  public static void swap(int[] ar , int m,int n){
        int tmp = ar[m];
        ar[m] = ar[n];
        ar[n] = tmp;
    }

    public static void print(int[] ar){
        for(int i:ar){
            System.out.print(i+" ");
        }
        System.out.println();
    }
1
2
3
4
5
6
7
8
9
10
11
12

字典序

• 描述

• 类似字符串排序，排列之间可以比较大小，参考字符串比较大小
• 上面的方法很难拿到指定一个排列的下一个排列(升序)，字典序可以更加容易的拿到，并通过不断拿到下一个字符串的方式，得到全排列。这里只给出拿到下一个排列的方法(findNext)

• 流程-------------------------------------------------------例子 2143

  • 1.从右向左找到相邻下标 a,b,且[a]<[b]-----------------[a]=1,a=1
  • 2.从b…n中寻找大于[a]的最小的数[c]-----------------------[c]=3,c=3
  • 3.交换值-----------------------------------------------------------2341
  • 4.a下标后的数升序排列----------------------------------------2314

    public static int[] findNext(int[] arr){
        if(arr==null||arr.length==0)return null;
        int[] ar = arr.clone();
//        swap1 是a
        int swap1 = -1;
        int len = ar.length;
        for (int i = len-1; i >=1; i--) {
            if(ar[i]>ar[i-1]){
                swap1 = i-1;
                break;
            }
        }
//        swap2 是c
        int swap2 = swap1+1;
        //如果这个就是排列中最大的，返回最小的排列
        if(swap1 == -1) {
            Arrays.sort(ar);
            return ar;
        };
//        找到swap2 
        for (int i = swap1; i < len; i++) {
            int tmp = ar[i];
            if(ar[swap1]<tmp&&tmp<ar[swap2]){
                swap2 = i;
            }
        }
//        交换
        swap(ar,swap1,swap2);
//        a坐标后的数升序
        int first = swap1+1;
        Arrays.sort(ar,first,len);
        return ar;
    }
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