java - 创建将 n 个用户放入 k 个组的所有可能方法

Question

给定 n 个用户(u_1、u_2、...、u_n)和 k 个组(g_1、g_2、...、g_k)，创建所有组的所有可能组合。基本上，最后，每个组合都是一个 Map ，其中第一个 Integer 是用户 ID，第二个 Integer 是组 ID。例如，[(u_1,g_1), (u_2,g_1).. ..,(u_n, g_1)] 是一种可能的组合。

会有k^n种组合。

我搜索并看到了类似的问题，但它们确实有一些不适用于我的问题的额外条件。就我而言，每组没有限制，也没有均匀或均匀分布。

您能推荐一种用 Java 快速完成此操作的方法吗？

谢谢

到目前为止我的尝试:我尝试为每个用户的每种可能性创建一个 for 循环，但我面临无法定义 for 循环数量的问题。

所以我切换到递归，但坚持为函数的内部调用创建参数。不过仍在努力。

请注意，这不是“n 选择 k”。 “n选k”是所有用户都相同，但这里的用户显然不相同。

---

好的。我为此创建了一个解决方案。基本上，这是一个动态规划问题。假设您已经为 j 个用户和 k 个位置创建了一个 map (组合)列表。要为 j+1 个用户和 k 个位置创建，需要 2 个循环:对于每个 Map，对于每个 i=1 到 k，Map.put(user_j+1, k))。 Is 既是递归的又是迭代的。递归，因为您需要将旧 map 传递给新迭代。就是这样。

Answer 1

这类问题的传统解决方案是使用递归:如果有 n = 0 个用户，唯一可能的分组就是空组。否则，取出第一个用户并为其他 n-1 个用户生成解决方案。使用子问题的解决方案，通过将第一个用户分配给 k 个可能组中的每一个来生成最终解决方案。

在代码中:

import java.util.*;

class Grouping {
    public static void main(String[] args) {
        List<?> groups = grouping(Arrays.asList(1,2,3), Arrays.asList(4,5,6,7));
        System.out.println(groups.size());
        System.out.println(groups);
    }

    static List<Map<Integer,Integer>> grouping(List<Integer> users, List<Integer> groups) {
        if (users.isEmpty()) {
            Map<Integer,Integer> empty = Collections.emptyMap();
            return Collections.singletonList(empty);
        } else {
            Integer user = users.get(0);
            List<Map<Integer,Integer>> subs = grouping(users.subList(1,users.size()), groups);

            List<Map<Integer,Integer>> solutions = new ArrayList<>();
            for (Integer group: groups) {
                for (Map<Integer,Integer> sub : subs) {
                    Map<Integer,Integer> m = new HashMap<>(sub);
                    m.put(user, group);
                    solutions.add(m);
                }
            }
            return solutions;
        }
    }
}