Create all possible ways of putting n users into k groups

algorithm, combinations, java

Solution

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

Problem

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.

Original source