java - 在 Java 中打印给定大小为 n 的整数数组中 r 元素的所有可能排列

Question

给定一个大小为 n 的数组，生成并打印数组中 r 元素的所有可能排列。

例如，如果 n 为 4，输入数组为 [0, 1, 2, 3]，r 为 3，则输出应为

[0, 1, 2]
[0, 1, 3]
[0, 2, 1]
[0, 2, 3]
[0, 3, 1]
[0, 3, 2]
[1, 0, 2]
[1, 0, 3]
[1, 2, 0]
[1, 2, 3]
[1, 3, 0]
[1, 3, 2]
[2, 0, 1]
[2, 0, 3]
[2, 1, 0]
[2, 1, 3]
[2, 3, 0]
[2, 3, 1]
[3, 0, 1]
[3, 0, 2]
[3, 1, 0]
[3, 1, 2]
[3, 2, 0]
[3, 2, 1]

输入数组中的所有元素都是整数，从 0 到 n-1。如何使用 Java 打印所有可能的排列？

重要提示:单个排列中所有元素的数量并不总是原始数组的大小。它小于或等于原始数组的大小。此外，每个排列中元素的顺序也很重要。

我在n=4和r=3时编写了一些代码。如果 n = 100 且 r = 50，我的代码将非常难看。当参数只有 n 和 r 时，有什么聪明的方法可以做到这一点吗？

public static void main(String[] args) {

    // original array
    ArrayList < Integer > items = new ArrayList < > ();

    // all permutations
    ArrayList < ArrayList < Integer >> allPermutations = new ArrayList < ArrayList < Integer >> ();

    // define the end item of the original array.
    // this is n, suppose it's 4 now.
    int endItem = 4;
    for (int i = 0; i < endItem; i++) {
        items.add(i);
    }


    // r means how many elements in each single permutation
    // suppose it's 3 now, i have to write for-loop three times
    // if r is 100, i have to write for-loop 100 times

    // first of the "r"
    for (int i = 0; i < items.size(); i++) {
        // second of the "r"
        for (int j = 0; j < items.size(); j++) {
            // can't be identical to i
            if (j == i)
                continue;

            // third of the "r"
            for (int k = 0; k < items.size(); k++) {
                // can't be identical to i or j
                if (k == i || k == j)
                    continue;

                // a single permutation
                ArrayList < Integer > singlePermutation = new ArrayList < > ();
                singlePermutation.add(items.get(i));
                singlePermutation.add(items.get(j));
                singlePermutation.add(items.get(k));

                // all permutations
                allPermutations.add(singlePermutation);

            }
        }
    }
    for (ArrayList < Integer > permutation: allPermutations) {
        System.out.println(permutation);
    }
    System.out.println(allPermutations.size());

}

Answer 1

将解决方案从问题移至答案:

Solution:

Thanks to older coder, I managed to find the solution.

public class PermutationTest10 {
    // a is the original array
    // k is the number of elements in each permutation
    public static ArrayList<ArrayList<Integer>> choose(ArrayList<Integer> a, int k) {
        ArrayList<ArrayList<Integer>> allPermutations = new ArrayList<ArrayList<Integer>>();
        enumerate(a, a.size(), k, allPermutations);
        return allPermutations;
    }

  // a is the original array
    // n is the array size
    // k is the number of elements in each permutation
    // allPermutations is all different permutations
    private static void enumerate(ArrayList<Integer> a, int n, int k, ArrayList<ArrayList<Integer>> allPermutations) {
        if (k == 0) {
            ArrayList<Integer> singlePermutation = new ArrayList<Integer>();
            for (int i = n; i < a.size(); i++){
                singlePermutation.add(a.get(i));
            }
            allPermutations.add(singlePermutation);
            return;
        }

      for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            enumerate(a, n-1, k-1, allPermutations);
            swap(a, i, n-1);
        }
    }  

  // helper function that swaps a.get(i) and a.get(j)
    public static void swap(ArrayList<Integer> a, int i, int j) {
        Integer temp = a.get(i);
        a.set(i, a.get(j));
        a.set(j, temp);
    }


  // sample client
    public static void main(String[] args) {

      // n is the end item of the array.
        // if n = 5, the array is [0, 1, 2, 3, 4, 5]
        // k is the number of elements of each permutation.
        int n =5;
        int k =3;

      // create original array
        ArrayList<Integer> elements = new ArrayList<> ();
        for (int i =0; i < n; i ++){
            elements.add(i);
        }

      ArrayList<Integer> a = new ArrayList<> ();
        for (int i = 0; i < n; i ++){
            a.add(elements.get(i));
        }
        System.out.println(choose(a, k));
    }
}