Java 打印出数组的所有排列

Print out all permutations of an Array

提问by

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.

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

My code for the permutation function is:

我的置换函数代码是：

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;
}

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

我应该在函数 main 中写一个循环，它会打印出 n！次？

采纳答案by Mshnik

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.

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

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

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

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.

我们注意到这将在 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;
    }
}

Sample input, output:

样本输入、输出：

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]

回答by Ankur Anand

I have followed this method most of the time .. (it's given by the Robert Sedgewick and Kevin Wayne. ).

我大部分时间都遵循这种方法..（这是由罗伯特塞奇威克和凯文韦恩给出的。）。

public class Permutations {

    // print N! permutation of the characters of the string s (in order)
    public  static void perm1(String s) { perm1("", s); }
    private static void perm1(String prefix, String s) {
        int N = s.length();
        if (N == 0) System.out.println(prefix);
        else {
            for (int i = 0; i < N; i++)
               perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
        }

    }

    // print N! permutation of the elements of array a (not in order)
    public static void perm2(String s) {
       int N = s.length();
       char[] a = new char[N];
       for (int i = 0; i < N; i++)
           a[i] = s.charAt(i);
       perm2(a, N);
    }

    private static void perm2(char[] a, int n) {
        if (n == 1) {
            System.out.println(a);
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            perm2(a, n-1);
            swap(a, i, n-1);
        }
    }  

    // swap the characters at indices i and j
    private static void swap(char[] a, int i, int j) {
        char c;
        c = a[i]; a[i] = a[j]; a[j] = c;
    }

However There is also an easier way to do this. May be you can work also around this

但是，还有一种更简单的方法可以做到这一点。也许你也可以解决这个问题

class PermutingArray {
    static void permutingArray(java.util.List<Integer> arrayList, int element) {
        for (int i = element; i < arrayList.size(); i++) {
            java.util.Collections.swap(arrayList, i, element);
            permutingArray(arrayList, element + 1);
            java.util.Collections.swap(arrayList, element, i);
        }
        if (element == arrayList.size() - 1) {
            System.out.println(java.util.Arrays.toString(arrayList.toArray()));
        }
    }

    public static void main(String[] args) {
        PermutingArray
                .permutingArray(java.util.Arrays.asList(9, 8, 7, 6, 4), 0);
    }
}

Working Example here .. IDeone Link

此处的工作示例.. IDeone 链接

回答by dened

The trick is to return a special value (falsein the code below) from nextPermwhen it was the last permutation (i.e. when array become sorted in descending order):

诀窍是false从nextPerm最后一次排列时（即数组按降序排序时）返回一个特殊值（在下面的代码中）：

import java.util.*;

public class Main {
    public static boolean nextPerm(List<Integer> a) {
        int i = a.size() - 2;
        while (i >= 0 && a.get(i) >= a.get(i + 1))
            i--;

        if (i < 0)
            return false;

        int j = a.size() - 1;
        while (a.get(i) >= a.get(j))
            j--;

        Collections.swap(a, i, j);
        Collections.reverse(a.subList(i + 1, a.size()));
        return true;
    }
    ...

Then you can use the loop (note that the array required be sorted in ascending order initially):

然后你可以使用循环（注意，数组最初需要按升序排序）：

    ...
    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(new Integer[] {1, 2, 3, 4});
        do {
            System.out.println(a);
        } while (nextPerm(a));
    }
}

You can try this code here: http://ideone.com/URDFsc

您可以在此处尝试此代码：http: //ideone.com/URDFsc