创建将n个用户划分为k个组的所有可能方法 [英] Create all possible ways of putting n users into k groups

问题描述

给定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快速做到这一点吗？ p>

谢谢

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

因此，我切换到递归，但是坚持为内部调用函数创建参数。

请注意，这不是 n选择k。 n选择k是指所有用户都相同，但此处用户显然不相同。

---

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

解决方案

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

在代码中：

  import java.util。*; 
 
类分组{
 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）; 
} 
 
静态List< Map< Integer，Integer>>分组（List< Integer>用户，List< Integer>组）{
 if（users.isEmpty（））{
 Map< Integer，Integer>空= Collections.emptyMap（）; 
 return Collections.singletonList（空）; 
} else {
整数user = users.get（0）; 
 List< Map< Integer，Integer>> subs = grouping（users.subList（1，users.size（）），组）; 
 
 List< Map< Integer，Integer>>解决方案= new ArrayList<>（）; （整数组：群组）的
 {{Map< Integer，Integer> sub：subs）的
 {
 Map< Integer，Integer> m =新的HashMap<>（sub）; 
 m.put（用户，组）； 
 solutions.add（m）; 
} 
} 
退货解决方案； 
} 
} 
} 
  

Given n users (u_1, u_2,..., u_n) and k groups (g_1, g_2, ..., g_k), create all possible combinations of all groups. basically, in the end, each combination is a Map<Integer,Integer>, where the first Integer is user ID, and the second Integer is group ID.For example, [(u_1,g_1), (u_2,g_1)....,(u_n, g_1)] is one possible combination.

There will be k^n combinations.

I searched and saw similar problems, but they do have some extra conditions that do not apply for my problem. In my case, there is no limit in each group, and there is no evenness or uniform distribution.

Can you suggest a quick way to do this in Java?

Thanks

My tries so far: I tried to create a for loop for each possibility for each user, but I face the problem that I cannot define the number of for loops.

So I switched to recursion, but stuck at creating parameters for inside calls to the functions. Still working on it though.

Please, also note that this is not "n choose k". "n choose k" is when all users are identical, but here users are obviously not identical.

---

OK. I created a solution for this. Basically, it's a dynamic programming problem. Assume you have created a List of Maps (combinations) for j users and k locations. TO create for j+1 users and k locations, need 2 loop: for each Map, for each i=1 to k, Map.put(user_j+1, k)). Is is both recursive and iterative. Recursive because you need to pass the old maps to the new iterations. That's it.

解决方案

The traditional solution to these kinds of problems is using recursion: If there are n = 0 users the only grouping possible is the empty group. Otherwise, take out the first user and generate the solution for the other n-1 users. Using the solution for the subproblem, generate the final solutions by assigning the first user to each of the k possible groups.

In code:

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

这篇关于创建将n个用户划分为k个组的所有可能方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！