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

Question

给定 n 个用户 (u_1, u_2,..., u_n) 和 k 个组 (g_1, g_2, ..., g_k)，创建所有组的所有可能组合。基本上，最后每个组合都是一个Map<Integer,Integer>，其中第一个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 个位置创建了一个地图列表（组合）。要为 j+1 个用户和 k 个位置创建，需要 2 个循环：对于每个 Map，对于每个 i=1 到 k，Map.put(user_j+1, k))。Is 既是递归的又是迭代的。递归，因为您需要将旧地图传递给新的迭代。就是这样。

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