智能生成组合的组合

Question

假设我有一个 30 名学生的班级，想要生成各种可能的方式将他们分成 5 人一组（顺序无关）。

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

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

我很了解 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 个不同的分区，每组 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]

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

Answer 2

这是一个老问题，但无论如何，为了记录，这就是我在 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]]]

Answer 3

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

// 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);
   }
}

可能不是最有效的；我会添加排序 &与亲自生成排列的代码进行比较。

Answer 4

一种可能性是找到所有组合来形成一个单独的组，然后遍历并生成不包含该单独组的成员的组合。类似于：

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 名学生组成 5 人一组，应该有 142,506 种组合。我的<讽刺>太棒了数学技能建议应该有大约 10^17 = 100 万亿个学生组组合 (30!/((5!^6)*6!); 30! 学生的排序，6 组 5 人的排序并不重要，并且这 6 组的顺序并不重要）。您可能会坐在那里等待这一切完成。