打印出阵列的所有排列 [英] Print out all permutations of an Array

问题描述

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

I am working on a program, and I have a function that swaps the positions in an Array of length that is input by a user. However, I am trying to figure out how to print out this function call N! times, which would list all the permutations in the function.

我的排列函数代码是：

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中写一个循环，将打印出来的n！时间？

Should I write a loop in function main, that will print this out n! times?

推荐答案

创建（或打印）数组的排列作为递归和迭代的组合比纯粹更容易完成反复。肯定有迭代方法可以实现，但组合起来却特别简单。具体来说，注意根据定义N！长度为N阵列的排列 - 第一个槽的N个选择，第二个槽的N-1选择等等。因此，对于阵列中的每个索引i，我们可以将算法分解为两个步骤 。

Creating (or printing) the permutations of an array is much easier done as a combination of recursively and iteratively than purely iteratively. There are surely iterative ways to do it, but it is particularly simple with a combination. Specifically, note that there are by definition N! permutations of a length N array - N choices for the first slot, N-1 choices for the 2nd, etc etc. So, we can break an algorithm down into two steps for each index i in the array.

1. 在子数组中选择一个元素 arr [i .... end] 成为数组的 ith 元素。用当前位于 arr [i] 的元素交换该元素。


2. 递归置换 arr [i + 1 ...结束] 。

1. Select an element in the sub-array arr[i....end] to be the ith element of the array. Swap that element with the element currently at arr[i].
2. Recursively permute arr[i+1...end].

我们注意到这将在O（N！）中运行，如在第一个呼叫中，将进行N个子呼叫，每个呼叫将进行N-1个子呼叫等。此外，每个元素最终都会在每个位置，并且只要进行交换，就不会有任何元素。重复。

We note that this will run in O(N!), as on the 1st call N sub calls will be made, each of which will make N-1 sub calls, etc etc. Moreover, every element will end up being in every position, and so long as only swaps are made no element will ever be duplicated.

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]

这篇关于打印出阵列的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！