【蓝桥杯】Java实现之全排列

以【1，2，3】位例子：全排列有

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

1,2,3的全排列可以看作是
   1,[2,3的全排列]
      [2,3]的全排列又可以看作是
         2,[3的全排列]—————对应123
         3,[2的全排列]—————对应132
   2,[1,3的全排列]
      [1,3]的全排列又可以看作是
         1,[3的全排列]—————对应213
         3,[1的全排列]—————对应231
   3,[1,2的全排列]
      [1,2]的全排列又可以看作是
         1,[2的全排列]—————对应312
         2,[1的全排列]—————对应321

package 全排列;

import java.lang.reflect.Array;
import java.util.Arrays;

public class example {

	public static void main(String[] args) {
		perm(new int[] {1,2,3},0,2);

	}
	public static void perm(int[] array,int start,int end) {
		if (start==end) {
			System.out.println(Arrays.toString(array));
		}else {
			for (int i = start; i <=end; i++) {
				//1,2,3的全排列这块相当于将其中一个提了出来。下次递归从start+1开始
				swap(array,start,i);
				perm(array,start+1,end);
				//这块是复原数组，为了保证下次另外的同级递归使用数组不会出错
				//这块可以通过树来理解，每次回退一步操作，交换回去
				swap(array,start,i);
			}
		}
	}

	public static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}

分两个步骤：
（1）确定第一位的字符
数组array从start到end的所有记录都可以出现在第一个位置，所以直接一个for循环，考虑了这所有的情况。在for循环中，swap方法就是交换i和start位置的数，保证当前i指向的记录出现在第一个位置，也就是start指向的位置
（2）剩下的记录继续做全排列
这个就是一个递归函数的调用，只需要修改起始位置，也就是start+1，因为start的位置已经放了记录，所以只需要继续做从start+1到end的全排列即可

题目描述：将编号为1~10的10本书排放在书架上，要求编号相邻的书不能放在相邻的位置。
请计算一共有多少种不同的排列方案。

注意，需要提交的是一个整数，不要填写任何多余的内容。

public class BookSort {

    public static void main(String[] args) {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        fullSort(arr, 0, arr.length - 1);
        System.out.println(res);
    }

    static int res = 0;

    static void fullSort(int[] arr, int start, int end) {
        // 递归终止条件
        if (start == end) {
            // 求出了全排列的一种情况，然后检查是否满足条件
            if (check(arr))
                res++;
            return;
        }
        for (int i = start; i <= end; i++) {
            swap(arr, start, i);
            fullSort(arr, start + 1, end);
            swap(arr, start, i);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static boolean check(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (Math.abs(arr[i] - arr[i - 1]) == 1)
                return false;
        }
        return true;
    }

}