ruby – 智能地生成组合的组合

发布时间：2020-12-17 02:58:07 所属栏目：百科来源：网络整理

导读：假设我有一个30个学生的班级,并希望生成一种可能的方式,将它们划分为5个组(顺序无关紧要). 我知道如何找到学生的所有组合,分别组成一个小组(http://www.merriampark.com/comb.htm).通过使用该迭代器和一些递归,我可以找到可能的组合组合的PERMUTATIONS.但是,

假设我有一个30个学生的班级,并希望生成一种可能的方式,将它们划分为5个组(顺序无关紧要).

我知道如何找到学生的所有组合,分别组成一个小组(http://www.merriampark.com/comb.htm).通过使用该迭代器和一些递归,我可以找到可能的组合组合的PERMUTATIONS.但是,选择组的顺序不相关,我想尽量缩短执行时间.那么如何找到可能组的唯一组合？

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

我很了解Ruby,Java / Python也不太了解.提前感谢任何建议！

解决方法

那么,(30C5 * 25C5 * 20C5 * 15C5 * 10C5 * 5C5)/ 6！ = 30！/(6！* 5！6)= 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]

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!