Algorithm to retrieve every possible combination of sublists of a two lists
- by sgmoore
Suppose I have two lists, how do I iterate through every possible combination of every sublist, such that each item appears once and only once.
I guess an example could be if you have employees and jobs and you want split them into teams, where each employee can only be in one team and each job can only be in one team. Eg
List<string> employees = new List<string>() { "Adam", "Bob"} ;
List<string> jobs = new List<string>() { "1", "2", "3"};
I want
Adam : 1
Bob : 2 , 3
Adam : 1 , 2
Bob : 3
Adam : 1 , 3
Bob : 2
Adam : 2
Bob : 1 , 3
Adam : 2 , 3
Bob : 1
Adam : 3
Bob : 1 , 2
Adam, Bob : 1, 2, 3
I tried using the answer to this stackoverflow question to generate a list of every possible combination of employees and every possible combination of jobs and then select one item from each from each list, but that's about as far as I got.
I don't know the maximum size of the lists, but it would be certainly be less than 100 and there may be other limiting factors (such as each team can have no more than 5 employees)
Update
Not sure whether this can be tidied up more and/or simplified, but this is what I have ended up with so far.
It uses the Group algorithm supplied by Yorye (see his answer below), but I removed the orderby which I don't need and caused problems if the keys are not comparable.
var employees = new List<string>() { "Adam", "Bob" } ;
var jobs = new List<string>() { "1", "2", "3" };
int c= 0;
foreach (int noOfTeams in Enumerable.Range(1, employees.Count))
{
var hs = new HashSet<string>();
foreach( var grouping in Group(Enumerable.Range(1, noOfTeams).ToList(), employees))
{
// Generate a unique key for each group to detect duplicates.
var key = string.Join(":" ,
grouping.Select(sub => string.Join(",", sub)));
if (!hs.Add(key))
continue;
List<List<string>> teams = (from r in grouping select r.ToList()).ToList();
foreach (var group in Group(teams, jobs))
{
foreach (var sub in group)
{
Console.WriteLine(String.Join(", " , sub.Key ) + " : " + string.Join(", ", sub));
}
Console.WriteLine();
c++;
}
}
}
Console.WriteLine(String.Format("{0:n0} combinations for {1} employees and {2} jobs" , c , employees.Count, jobs.Count));
Since I'm not worried about the order of the results, this seems to give me what I need.
