智能地生成组合的组合

假设我有一个30个学生的class级，并希望生成一种可能的方式，将它们划分为5个组（顺序无关紧要）。

我知道如何找到学生的所有组合，分别组成一个小组（ http://www.merriampark.com/comb.htm ）。 通过使用该迭代器和一些递归，我可以找到可能的组合组合的PERMUTATIONS。 但是，选择组的顺序不相关，我希望最小化执行时间。 那么如何找到可能组的独特组合？

上面的算法使用词典排序来避免生成重复的组合……有没有办法可以在组上而不是在对象上使用这个想法？

我很了解Ruby，Java / Python也不太了解。 提前感谢您的任何建议！

Answer 1

那么，（30 _C 5 * 25 _C 5 * 20 _C 5 * 15 _C 5 * 10 _C 5 * 5 _C 5）/ 6！ = 30！/（6！* 5！ ⁶ ）= 123,378,675,083,039,376个不同的分区，每组30个，每组5个，因此无论使用何种方法，生成它们都需要一些时间。

但是，一般来说，选择这样一个分区的一个好方法是对元素使用一些排序，找到最高的未分组元素的分组，然后对其余元素进行分组。

  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] 

这样，您只生成一次每个分区

Answer 2

这是一个老问题，但无论如何，为了记录，这就是我在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 

我使用枚举器，因为输出可以非常快速地增长，严格的输出（例如数组）将没有用。 一个用法示例：

 >> 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]]] 

Answer 3

您可以对排列进行一些后处理。 一些伪代码（用你选择的语言实现……）：

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

可能不是最有效的; 我将添加排序和比较与个人生成排列的代码。

Answer 4

一种可能性是找到所有组合以形成单个组，然后通过并生成不包含该组个体的组合。 就像是：

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

它不是最有效的方法，但它应该生成所有组的组合。 我怀疑如果要生成临时组合列表，可以获得更好的性能，其中所有不可能发生的组都被删除，但这会更复杂一些。

稍微一点，应该有142,506个组合，30个学生组成一个单独的5组。我的 awesome 数学技能表明应该有大约10 ^ 17 = 100千万亿组的学生组（ 30！/（（5！^ 6）* 6！）; 30！学生的排序，6组5的排序无关紧要，这6组的排序无关紧要）。 你可能会坐在那儿等待这个完成。