在 Java 中生成无冗余的所有位置组合

Question

我想要一个算法来显示所有可能的组合。一个人不能同时从事多项工作。在下面的示例中，如果只有 5 个人和 3 个工作。所以有 5 X 4 X 3 种组合，所以有 60 种组合。该解决方案应在 Java 中完成。我可以使用 Guava 库。我看开发实践特别好（不只是解决方案）。

输入：

John、Peter、Dylan、Bryan、Pharell 和工作 A、工作 B、工作 C

输出：

Solution 1:
Job A: John
Job B: Peter
Job C: Dylan

Solution 2:
Job A: Pharell
Job B: John
Job C: Peter

Solution 3:
Job A: John
Job B: Pharell
Job C: Peter

...

Solution 60:
Job A: John
Job B: Pharell
Job C: Bryan

Answer 1

在这里您可以看到基于 amit's answer for subsets and guava - Collections2 排列的解决方案：

import com.google.common.collect.Collections2;

import java.util.*;

public class Test {
    private static void getSubsets(List<String> superSet, int idx, Set<String> current, List solution) {
        if (current.size() == 3) {
            solution.add(new HashSet<>(current));
            return;
        }
        if (idx == superSet.size()) {
            return;
        }
        String x = superSet.get(idx);
        current.add(x);
        getSubsets(superSet, idx + 1, current, solution);
        current.remove(x);
        getSubsets(superSet, idx + 1, current, solution);
    }

    public static List<Set<Integer>> getSubsets(List<String> superSet) {
        List res = new ArrayList<>();
        getSubsets(superSet, 0, new HashSet<>(), res);
        return res;
    }

    public static void main(String[] args) {
        List<String> initialSet = new ArrayList<String>() {{
            add("John");
            add("Peter");
            add("Dylan");
            add("Bryan");
            add("Pharell");
        }};
        List<Set<Integer>> subsets = getSubsets(initialSet);
        int counter = 1;
        for (Set s : subsets) {
            Collection<List<String>> results = Collections2.permutations(s);
            for (List<String> words : results) {
                System.out.println("Solution " + counter++);
                System.out.println("Job A: " + words.get(0));
                System.out.println("Job B: " + words.get(1));
                System.out.println("Job C: " + words.get(2));
                System.out.println();
            }
        }
    }
}

因此，因为您始终按此顺序排列 A、B 和 C，所以在实施过程中忽略了它们。只有当我打印输出时你才能看到它们。所以，问题就变成了：找到一个 5 元素集合的所有 3 元素排列。

首先，为一个5元集合生成了所有的3元集合，然后对每个得到的集合进行置换。

在 Java 中生成无冗余的所有位置组合

Generate all combinations of place without redundancy in Java

java

algorithm

combinations

list

guava