递归－全排列

 本文转载于：http://shenyu.iteye.com/blog/193780

 

 

 

将指定数组全排列打印，此处使用递归算法。

其核心是，轮流将数组中每个数字放在第一位上，然后调用剩下n-1个数字的全排列。以此形成递归。

以下是代码：

class Arrangement {
    public static void main(String[] args) {
        int[] a = {1,2,3,4};
        print(a,0,true);
    }


    public static void print(int [] a, int offSet, boolean needPrint) {
        if(needPrint)println(a);    //如果需要则，打印数组
        if(offSet == a.length-1) {    //递归结束条件
            return;
        }

        for(int i=offSet; i<a.length; i++) {
            rotate(a,offSet);    //数组第n位之后的元素，轮换充当n的元素
            //对数组在第n+1位后的元素递归调用排列算法，最后一遍仅仅是为了将数组复原成初始的样子，因此最后一次不需要打印，前面已经打过了
            print(a,offSet + 1, i != a.length-1);
        }

    }

    public static void rotate(int[] a, int offSet) {    //从指定位置开始，所有的元素右移一次，最后的元素移动到初始指定的位置
        int temp = a[a.length-1];
        for(int i=a.length-1; i>offSet; i--) a[i] = a[i-1];
        a[offSet] = temp;
    }

    public static void println(int[] a) {    //打印数组
        for(int i: a) System.out.print(i + " " );
        System.out.println();
    }
}

class Arrangement {
    public static void main(String[] args) {
        int[] a = {1,2,3,4};
        print(a,0,true);
    }
   

    public static void print(int [] a, int offSet, boolean needPrint) {
        if(needPrint)println(a);    //如果需要则，打印数组
        if(offSet == a.length-1) {    //递归结束条件
            return;   
        }

        for(int i=offSet; i<a.length; i++) {   
            rotate(a,offSet);    //数组第n位之后的元素，轮换充当n的元素
            //对数组在第n+1位后的元素递归调用排列算法，最后一遍仅仅是为了将数组复原成初始的样子，因此最后一次不需要打印，前面已经打过了
            print(a,offSet + 1, i != a.length-1);   
        }

    }

    public static void rotate(int[] a, int offSet) {    //从指定位置开始，所有的元素右移一次，最后的元素移动到初始指定的位置
        int temp = a[a.length-1];
        for(int i=a.length-1; i>offSet; i--) a[i] = a[i-1];
        a[offSet] = temp;
    }

    public static void println(int[] a) {    //打印数组
        for(int i: a) System.out.print(i + " " );
        System.out.println();
    }
}