问题描述
比方说,我有一班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知道如何找到所有学生组合以单独组成一个小组()。通过使用该迭代器和一些递归,我可以找到可能的组组合的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 5 * 25 5 * 20 5 * 15 5 * 10 5 * 5 5)/ 6! = 30!/(6!* 5!)= 123,378,675,083,039,376的30个不同组成部分分成5组,因此无论使用哪种方法,生成它们都将花费一些时间。
Well, there's (305*255*205*155*105*55)/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
这篇关于智能生成组合的组合的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!