intelligently generating combinations of combinations

Question

Let's say I have a class of 30 students and want generate every possible way in which they can be partitioned into groups of 5 (order is irrelevant).

I know how to find all the combinations of students to form one group individually (http://www.merriampark.com/comb.htm). By using that iterator and some recursion, I can find PERMUTATIONS of the possible group combinations. However, order in which the groups are selected isn't relevant and I'd like to minimize my execution time. So how do I find the unique COMBINATIONS of the possible groups?

The above algorithm uses lexicographical ordering to avoid generating duplicate combinations... is there a way that I can use that idea on groups instead of on objects?

I know Ruby well and Java/Python less well. Thanks in advance for any advice!

Answer 1

You could do some post-processing on the permutations. Some pseudo-code (implement in the language of your choice...):

// We have a list of lists called 'permutations'
// combinations is an (empty) list of lists
for each permutation in permutations
{
   sortedPermutation = permutation.sort()
   if (! combinations.find(sortedPermutation) )
   {
       combinations.add(sortedPermutation);
   }
}

Probably not the most efficient; I'd add the sort & compare to the code that generates the permutations personally.

Answer 2

One possibility would be to find all combinations to form an individual group, then go through and generate combinations that don't contain members of that individual group. Something like:

List<List<Student>> combinations=Combinations(students);
public void GenerateCombinations(int startingIndex, List<List<Student>> currentGroups, int groupsLeft)
{
    if(groupsLeft==0) ProcessCombination(currentGroups);

    for(int i=startingIndex; i<combinations.Count; i++)
    {
        if combinations[i] does not contain a student in current groups
            GenerateCombinations(i+1, currentGroups + combinations[i], groupsLeft -1);
    }
}

It won't be the most efficient method to go about it, but it should generate all combinations of groups. I suspect better performance could be had if you were to generate temporary lists of combinations, where in all groups that can't occur were removed, but that would be a bit more complex.

As a slight aside, there should be 142,506 combinations of 30 students to form a single group of 5. My <sarcasm> awesome </sarcasm> math skills suggest that there should be about 10^17 = 100 quadrillion combinations of groups of students (30!/((5!^6)*6!); 30! orderings of students, ordering of 6 groups of 5 does not matter, and ordering of those 6 groups doesn't matter). You might be sitting there a while waiting for this to finish.

Answer 3

Well, there's (30_C5*25_C5*20_C5*15_C5*10_C5*5_C5)/6! = 30!/(6!*5!⁶) = 123,378,675,083,039,376 different partitons of 30 into groups of 5, so generating them all will take some time, no matter what method you use.

In general, though, a good method to selecting such a partition is to use some ordering on the elements, and find the grouping for the highest ungrouped element, and then group the rest.

  find_partition = lambda do |elts|
  if elts.empty?
   [[]]
  else
   highest = elts.pop
   elts.combination(4).map do |others|
   find_partition[elts - others].map { |part| part << [highest,*others] }
   end.inject(:+)
  end
  end
  find_partition[(1..30).to_a]

This way you're only generating each partition once