数组全排列问题

/* 全排列问题。

     设R = {r1,r2,...rn} 是要进行排列的n个元素，Ri = R-{ri}。集合X中元素的全排列记为 perm(X)。

     (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri得到的排列。R的全排列可归纳定义如下：

     当 n =1时，perm(R)=(r)，其中r是集合R中惟一的元素

     当 n > 1时,perm(R)由(r1)perm(R1),(r2)perm(R2)... (rn)perm(Rn)构成。

• 
  

     例：

             R = {1,2,3}, n = 3

             n>1，由题得: 1perm(2,3), 2perm(1,3) 3perm(1,2)

                     即：      1                        2                    3

                           2        3                1    3              1    2

                         1            2            3      1          2        1

• 
  

             则 全排列共有6 种方式

整体思路：
采取分治的思想。 例 {1,2,3}的全排列。 我们先把 1择出来，排列23 即 1, {2,3} 2,{1,3}, 3 {1,2}
1 {2,3} 2 {1,3} 3 {1,2}
1 2 {3} 1 3 {2} ， 2 1 {3} 2 3 {1} ， 3 1 {2} 3 2 {1}
给三个指针 k,m,j
k指向数组头，m指向数组最后一个元素，j用来缩小规模。

/
public class SortQuestion {
public static void swap_Ar(int arr[],int i,int j ){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/**

@param arr
@param k :代表第一个元素的下标
@param m : 最后一个元素的下标
/
public static void perm(int arr[],int k,int m){
if (k == m) {
for (int i = 0; i <=m ; i++) {
System.out.print(arr[i]);
}
System.out.println();
}else{
for (int j = k; j <=m ; j++) {
swap_Ar(arr,j,k); //1,2,3
// k+1 使其规模减小。
perm(arr,k+1,m);
swap_Ar(arr,j,k);
}
}
}
public static void main(String[] args) {
int arr[] = new int[]{1,2,3};
perm(arr,0,arr.length-1);
}
}