java - 如何显示数组的所有可能排列

Question

我正在研究 Java 中的排列。我的程序应该生成长度为n的数组的所有可能排列，并安排r个排列。

这是一个例子。对于具有这 12 个元素的数组

string  Mywords[] =("love" ,"guy" ,"cow","hen","dog","antelope","cat" "rat",welcome","thank","you","all");

在哪里

n=12, r=7

选择 12 个元素中的 7 个来创建阵列的 12 种可能变化。

=>> 输出可能是形式（可能的情况）

1. （爱，人，牛，母鸡，狗，羚羊，猫）
2. （爱，牛，家伙，母鸡，狗，羚羊，猫）
3. （爱，母鸡，人，牛，狗，羚羊，猫）
4. （爱，狗，母鸡，人，牛，羚羊，猫）
5. （爱，谢谢，狗，母鸡，家伙，牛，欢迎）
6. ：
7. ：
8. ：
9. ：
10. ：
11. ：
12. P(n,r)

如何打印所有可能的结果？

Answer 1

下面的代码改编自这个 SO question 的答案。

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

该问题使用整数列表。在下面的代码中，我基本上只替换Integer为String.

请注意，12 个元素的列表中 7 个元素的排列数接近 350 万，这需要时间。因此，在下面的代码中，我从五个元素列表中生成三个元素的排列。

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public static List<List<String>> choose(List<String> a, int k) {
        List<List<String>> allPermutations = new ArrayList<List<String>>();
        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(List<String> a,
                                  int n,
                                  int k,
                                  List<List<String>> allPermutations) {
        if (k == 0) {
            List<String> singlePermutation = new ArrayList<>();
            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(List<String> a, int i, int j) {
        String temp = a.get(i);
        a.set(i, a.get(j));
        a.set(j, temp);
    }

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

        // create original array
        List<String> elements = new ArrayList<>(List.of("love",
                                                        "guy",
                                                        "cow",
                                                        "hen",
                                                        "dog"));
        int n = elements.size();

        // k is the number of elements of each permutation.
        int k = 3;

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

运行上面的代码会产生以下输出。

[hen, dog, love]
[guy, dog, love]
[cow, dog, love]
[dog, guy, love]
[hen, guy, love]
[cow, guy, love]
[dog, cow, love]
[guy, cow, love]
[hen, cow, love]
[dog, hen, love]
[guy, hen, love]
[cow, hen, love]
[hen, love, guy]
[dog, love, guy]
[cow, love, guy]
[love, dog, guy]
[hen, dog, guy]
[cow, dog, guy]
[love, cow, guy]
[dog, cow, guy]
[hen, cow, guy]
[love, hen, guy]
[dog, hen, guy]
[cow, hen, guy]
[hen, love, cow]
[guy, love, cow]
[dog, love, cow]
[love, guy, cow]
[hen, guy, cow]
[dog, guy, cow]
[love, dog, cow]
[guy, dog, cow]
[hen, dog, cow]
[love, hen, cow]
[guy, hen, cow]
[dog, hen, cow]
[dog, love, hen]
[guy, love, hen]
[cow, love, hen]
[love, guy, hen]
[dog, guy, hen]
[cow, guy, hen]
[love, cow, hen]
[guy, cow, hen]
[dog, cow, hen]
[love, dog, hen]
[guy, dog, hen]
[cow, dog, hen]
[hen, love, dog]
[guy, love, dog]
[cow, love, dog]
[love, guy, dog]
[hen, guy, dog]
[cow, guy, dog]
[love, cow, dog]
[guy, cow, dog]
[hen, cow, dog]
[love, hen, dog]
[guy, hen, dog]
[cow, hen, dog]