智能生成组合的组合 [英] intelligently generating combinations of combinations

问题描述

比方说，我有一班30名学生，并且希望生成各种可能的方式将他们分成5组（顺序无关）。

Let's say I have a class of 30 students and want generate every possible way in which they can be partitioned into groups of 5 (order is irrelevant).

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

I know how to find all the combinations of students to form one group individually (http://www.merriampark.com/comb.htm). By using that iterator and some recursion, I can find PERMUTATIONS of the possible group combinations. However, order in which the groups are selected isn't relevant and I'd like to minimize my execution time. So how do I find the unique COMBINATIONS of the possible groups?

上述算法使用字典顺序以避免生成重复的组合...有没有办法我可以使用

The above algorithm uses lexicographical ordering to avoid generating duplicate combinations... is there a way that I can use that idea on groups instead of on objects?

我对Ruby和Java / Python不太了解。预先感谢您的任何建议！

I know Ruby well and Java/Python less well. Thanks in advance for any advice!

推荐答案

好吧，这里有（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组，因此无论使用哪种方法，生成它们都将花费一些时间。

Well, there's (30_C5*25_C5*20_C5*15_C5*10_C5*5_C5)/6! = 30!/(6!*5!⁶) = 123,378,675,083,039,376 different partitons of 30 into groups of 5, so generating them all will take some time, no matter what method you use.

但是，通常，选择这种分区的一种好方法是对元素使用某种排序，找到最高未分组元素的分组，然后将其余分组。 / p>

In general, though, a good method to selecting such a partition is to use some ordering on the elements, and find the grouping for the highest ungrouped element, and then group the rest.

     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]

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

This way you're only generating each partition once

这篇关于智能生成组合的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！