ruby - 智能生成组合的组合

Question

假设我的类(class)有 30 名学生，我想生成每一种可能的方式，将他们分成 5 人一组(顺序无关紧要)。

我知道如何找到所有学生的组合以单独组成一个小组 (http://www.merriampark.com/comb.htm)。通过使用该迭代器和一些递归，我可以找到可能的组组合的 PERMUTATIONS。但是，选择组的顺序无关紧要，我想尽量减少执行时间。那么我如何找到可能组的独特组合呢？

上述算法使用字典顺序来避免生成重复组合...有没有一种方法可以将这个想法用于组而不是对象？

我对 Ruby 很了解，对 Java/Python 不太了解。在此先感谢您的任何建议!

Answer 1

嗯，有 (30_C5*25_C5*20_C5*15_C5 *10_C5*5_C5)/6! = 30!/(6!*5!⁶) = 123,378,675,083,039,376 个不同的 partitons，每组 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]

这样你只生成每个分区一次