智能地生成组合的组合

Question

假设我有一个30个学生的班级,并希望生成一种可能的方式,将它们划分为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]

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