打印出数组的所有排列

一尘不染

打印出数组的所有排列

algorithm

我正在开发一个程序，并且有一个函数可以交换用户输入的长度数组中的位置。但是，我试图弄清楚如何打印此函数调用N！时间，它将列出函数中的所有排列。

我的置换函数代码为：

static void nextPerm(int[] A){
    for( int i = (n-1); i > 0; i-- ){
        if( A[i] < A[i+1] ){
            A[i] = pivot;
            continue;
        }
        if( A[i] >= A[i+1] ){
            reverseArray(A);
            return;
        }
    }

    for( int i = n; i > 0; i--){
        if( A[i] > pivot ){
            A[i] = successor;
            continue;
        }
    }

    Swap(pivot, successor);

    int[] B = new int[pivot+1];
    reverseArray(B);

    return;
}

我应该在main函数中编写一个循环，将其打印出来！时间？

阅读 186

2020-07-28

共1个答案

一尘不染

创建（或打印）数组的排列比单纯地迭代和循环地结合起来要容易得多。确实有迭代的方法可以做到这一点，但是结合使用起来特别简单。具体来说，请注意，根据定义，这里有N！长度为N的数组的排列-
第一个插槽为N个选择，第二个插槽为N-1个选择，依此类推。因此， 对于数组中的每个索引i ，我们可以将算法分解为两步。

在子数组中选择一个元素作为数组arr[i....end]的ith元素。将该元素与当前位于的元素交换arr[i]。
递归置换arr[i+1...end]。

我们注意到这将在O（N！）中运行，因为在第一次调用时将进行N个子调用，每个子调用将进行N-1个子调用，依此类推。此外，每个元素最终都将位于每个位置，并且只要进行交换，就不会重复任何元素。

public static void permute(int[] arr){
    permuteHelper(arr, 0);
}

private static void permuteHelper(int[] arr, int index){
    if(index >= arr.length - 1){ //If we are at the last element - nothing left to permute
        //System.out.println(Arrays.toString(arr));
        //Print the array
        System.out.print("[");
        for(int i = 0; i < arr.length - 1; i++){
            System.out.print(arr[i] + ", ");
        }
        if(arr.length > 0) 
            System.out.print(arr[arr.length - 1]);
        System.out.println("]");
        return;
    }

    for(int i = index; i < arr.length; i++){ //For each index in the sub array arr[index...end]

        //Swap the elements at indices index and i
        int t = arr[index];
        arr[index] = arr[i];
        arr[i] = t;

        //Recurse on the sub array arr[index+1...end]
        permuteHelper(arr, index+1);

        //Swap the elements back
        t = arr[index];
        arr[index] = arr[i];
        arr[i] = t;
    }
}

样本输入，输出：

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

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

2020-07-28