智能生成组合的组合

假设我有一个30名学生的班级，并希望生成他们可以分成5个组的每种可能的方式（顺序无关紧要）。智能生成组合的组合

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

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

我很熟悉Ruby和Java/Python。预先感谢您的任何建议！

来源

2009-10-26 Jordan Smith

也许看看这里，特别是'multiset'功能。这是Perl，但它应该给你一些代码戳在：http://search.cpan.org/perldoc/Math::Combinatorics – Telemachus

谢谢...知道这是一个“multiset”将使我的谷歌搜索更好。 –

那么，有（30 _ç 5 * 25 _Ç 5 * 20 _Ç 5 * 15 _Ç 5×10 _Ç 5 * 5 _Ç 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]

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

来源

2009-10-26 02:54:01 rampion

你能否详细说明为什么它不只是30c5？自2001年以来我没有看过组合数学！ – Josh

那么，有30c5的选择第5组的方式5,25c5，...，10c5选择第5组的方式5，以及5c5 = 1选择最后一种方式。但是，由于我们正在进行分区，因此我们不关心我们获得这些组的顺序。因为有6个！订购6组的方式，我们除以6！这在帖子中给出了扩展产品。 – rampion

感谢rampion ......使用这个数学，我能够说服我的项目负责人，我们需要采取另一种方法来提高可伸缩性。 –

你可以对排列做一些后期处理。一些伪代码（以您选择的语言实现...）：

// We have a list of lists called 'permutations' 
// combinations is an (empty) list of lists 
for each permutation in permutations 
{ 
    sortedPermutation = permutation.sort() 
    if (! combinations.find(sortedPermutation)) 
    { 
     combinations.add(sortedPermutation); 
    } 
}

可能不是最有效的;我会添加排序&比较生成排列个人的代码。

来源

2009-10-26 00:24:59 Josh

一种可能性是找到所有组合来形成单个组，然后通过并生成不包含该单个组的成员的组合。例如：

List<List<Student>> combinations=Combinations(students); 
public void GenerateCombinations(int startingIndex, List<List<Student>> currentGroups, int groupsLeft) 
{ 
    if(groupsLeft==0) ProcessCombination(currentGroups); 

    for(int i=startingIndex; i<combinations.Count; i++) 
    { 
     if combinations[i] does not contain a student in current groups 
      GenerateCombinations(i+1, currentGroups + combinations[i], groupsLeft -1); 
    } 
}

它不是最有效的方法，但它应该生成所有组的组合。如果您要生成临时的组合列表，我怀疑可能会有更好的性能，在所有不可能出现的组中都会删除这些组合，但这会稍微复杂一点。

作为轻微一旁，应该有30名学生142506个组合以形成5我<讽刺的单组>真棒< /讽刺>数学技能建议应该是大约10^17 = 100个万亿的组合（30！/！（（5！^ 6）* 6！）; 30！学生排序，6组5个排序无关紧要，这6组排序无关紧要）。你可能会坐在那里等待这个完成。

来源

2009-10-26 01:55:44 CoderTao

这是一个老问题，但无论如何，备案，这就是我将它在Ruby中：

class Array 
    def groups_of_size(n) 
    Enumerator.new do |yielder| 
     if self.empty? 
     yielder.yield([]) 
     else 
     self.drop(1).combination(n-1).map { |vs| [self.first] + vs }.each do |values| 
      (self - values).groups_of_size(n).each do |group| 
      yielder.yield([values] + group) 
      end 
     end 
     end 
    end 
    end 
end

我使用枚举器是因为输出可以非常快速地增长，所以严格的输出（例如数组）将不会有用。一个用法示例：

>> pp [0, 1, 2, 3, 4, 5].groups_of_size(3).to_a 
=> 
[[[0, 1, 2], [3, 4, 5]], 
[[0, 1, 3], [2, 4, 5]], 
[[0, 1, 4], [2, 3, 5]], 
[[0, 1, 5], [2, 3, 4]], 
[[0, 2, 3], [1, 4, 5]], 
[[0, 2, 4], [1, 3, 5]], 
[[0, 2, 5], [1, 3, 4]], 
[[0, 3, 4], [1, 2, 5]], 
[[0, 3, 5], [1, 2, 4]], 
[[0, 4, 5], [1, 2, 3]]]

来源

2011-05-06 16:01:09 tokland

智能生成组合的组合

回答

相关问题