[算法]-全排列

从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

排列组合公式：

递归

这是一个原地排列，递归过程如下：

假设排列{1,2,3},先选定第一个位置的元素，有三种可能，用exchange方法交换元素位置来选择一个元素（三种可能的其中一个），选定第一个元素后递归调用该方法来选定第二个元素，然后递归来选择第三个元素。至此我们得到了一个结果，我们需要将list还原，来继续遍历其他可能性。

最右边圈住的过程就是一个完整递归的过程。

java实现：

package algos;

/**
 * @author jiaxuehui
 * @version 1.0
 * @Description 全排序
 * @Date 03/12/2018 10:44 PM
 */
public class permutation<T> {

    public static<T> void fullPermutation(T[] list){
        fullPermutation(list, 0);
    }

    public static<T> void fullPermutation(T[] list, int curr){
       if(curr == list.length-1){
           System.out.print("\n");
           for (int i=0;i<list.length;i++) {
               System.out.print(list[i]+" ");
           }
           System.out.print("\n");
       }
       for (int i = curr; i < list.length;i++){  //设curr前的部分都已经排列，排列curr之后的字符
           exchange(list, i, curr); //当前的位置可能是后边的任何一个数字，将后边的数字依次放在该位置。
           System.out.print(curr);
           fullPermutation(list, curr+1);//交换后以当前的list继续排列后边一位
           exchange(list, i,curr);//恢复list
       }
    }

    private static<T> void exchange(T[] list, int i, int j){
        T tmp = list[i];
        list[i] = list[j];
        list[j] = tmp;
    }

    public static void main(String arg[]){
        Integer[] list={1,2,3};
        permutation.fullPermutation(list);
    }
}