打印出数组的所有排列组合

Question

我正在编写一个程序，其中有一个函数可以交换由用户输入长度的数组中的位置。但是，我正试图弄清楚如何多次调用此函数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;
}

我应该在主函数中写一个循环，以便将此内容打印出n！次吗？

- user4309460

---

示例输入：输入数组长度：5 - user4309460

输出：（1，3，5，2，4） （1，4，2，5，3） （2，4，1，3，5） （2，5，3，1，4） （3，1，4，2，5） （3，5，2，4，1） （4，1，3，5，2） （4，2，5，3，1） （5，2，4，1，3） （5，3，1，4，2） - user4309460

这段代码的隐含意义是什么：int[] B = new int[pivot+1]; reverseArray(B);？这会将零数组反转，不是吗？reverseArray(A) - 这看起来也很奇怪...我建议你使用我的答案中的实现，我已经进行了充分测试，它可以按预期工作。 - dened

Answer 1

使用递归和迭代的组合比纯迭代更容易创建（或打印）数组的排列。当然，可以通过迭代方式完成，但与组合相比，它特别简单。具体来说，需要注意一个长度为N的数组的定义是有N！种排列方式 - 第一个位置有N个选择，第二个位置有N-1个选择，以此类推。因此，我们可以将算法分解为两个步骤 对于数组中的每个索引i。

1. 从子数组arr[i....end]中选择一个元素作为数组的第i个元素。将该元素与当前位于arr[i]的元素交换。
2. 递归地对arr[i+1...end]进行排列。

我们注意到这将在O(N!)下运行，因为在第1次调用中将进行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]

- Mshnik

---

我正在尝试做到这一点，而不使用java.utl.Arrays包。 - user4309460

它不使用util.arrays... - Zizouz212

我的函数只能有参数 Int[] A。 - user4309460

1. 用手写版本替换Arrays.toString(..)。它实际上是一样的，只是手动实现。
2. permute函数确实只有一个类型为'int[]'的参数。创建辅助函数是否被禁止？

- Mshnik

这是一个惊人的答案！非常感谢。 - droidnoob

Answer 2

我大多数时候都遵循这种方法...(它是由Robert Sedgewick和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;
    }

然而，这也有一种更简单的方法可以实现。也许你可以围绕这个问题进行工作。

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

这里有一个工作示例.. IDeone链接

- Ankur Anand

---

第二个解决方案非常紧凑！展示了您在Java API使用方面的高超技能。 - Hungry Coder

Answer 3

关键是在nextPerm中当数组按降序排序时返回一个特殊值（在下面的代码中为false），以表示这是最后一个排列：

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

然后您可以使用循环（注意，所需数组必须最初按升序排序）：

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

你可以在这里尝试此代码：http://ideone.com/URDFsc

- dened