Geek Answers Handbook

Intelligently generating combinations of combinations

Let's say I have a class of 30 students and you want to generate all the possible ways in which they can be divided into groups of 5 (the order does not matter).

I know how to find all the combinations of students to form one group separately ( http://www.merriampark.com/comb.htm ). Using this iterator and some recursion, I can find the PERMUTATIONS of possible group combinations. However, the order in which the groups are selected does not matter, and I would like to minimize the execution time. So, how do I find unique COMBINATIONS of possible groups?

The above algorithm uses lexicographic ordering to avoid generating duplicate combinations ... is there a way I can use this idea for groups and not for objects?

I know Ruby and Java / Python well. Thank you in advance for any advice!

+4
source share
4 answers

Well, there (30 C 5 * 25 C 5 * 20 C 5 * 15 C 5 * 10 <sub> Ssub> 5 * 5 <sub> Ssub> 5) / 6! = 30! / (6! * 5! 6 ) = 123,378,675,083,039,376 of different scores of 30 in groups of 5, so it will take some time to create them, regardless of which method you use.

In general, a good method for choosing such a section is to use some order for the elements and find the grouping for the highest non-group element, and then group the others.

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]

Thus, you generate each section only once

+5
source

This is an old question, but anyway, to write how I would do it in Ruby:

 class Array def groups_of_size(n) Enumerator.new do |yielder| if self.empty? yielder.yield([]) else self.drop(1).combination(n-1).map { |vs| [self.first] + vs }.each do |values| (self - values).groups_of_size(n).each do |group| yielder.yield([values] + group) end end end end end end

I use an enumerator because the output can grow very quickly, strict output (like an array) will not be useful. Usage example:

 >> pp [0, 1, 2, 3, 4, 5].groups_of_size(3).to_a => [[[0, 1, 2], [3, 4, 5]], [[0, 1, 3], [2, 4, 5]], [[0, 1, 4], [2, 3, 5]], [[0, 1, 5], [2, 3, 4]], [[0, 2, 3], [1, 4, 5]], [[0, 2, 4], [1, 3, 5]], [[0, 2, 5], [1, 3, 4]], [[0, 3, 4], [1, 2, 5]], [[0, 3, 5], [1, 2, 4]], [[0, 4, 5], [1, 2, 3]]]
+1
source

You can do some post processing on permutations. Some pseudo codes (implement in your chosen language ...):

 // 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 effective; I would add sorting and compare the code that generates the permutations personally.

0
source

One possibility would be to find all the combinations to form a separate group, then go through and create combinations that do not contain members of this separate group. Sort of:

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

This is not the most efficient method for this, but it should generate all combinations of groups. I suspect that better performance can be achieved if you have to create temporary lists of combinations where, in all groups that cannot occur, have been deleted, but that would be a little more complicated.

As a small aspect, there must be 142,506 combinations of 30 students to form one group of 5. My <sarcasm> awesome </sarcasm> math skills suggest that there should be about 10 ^ 17 = 100 quadrillion combinations of student groups (30! / ((5! ^ 6) * 6!), 30! Ordering students, ordering 6 groups of 5 does not matter, and ordering these 6 groups does not matter). Perhaps you are sitting there, waiting for it to end.

0
source

More articles:


All Articles