4

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

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

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

我很了解 Ruby，而不太了解 Java/Python。提前感谢您的任何建议！

4

4 回答 4

5

嗯，有 (30 C 5*25 C 5*20 C 5*15 C 5*10 C 5*5 C 5)/6！= 30!/(6!*5! 6 ) = 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-26T02:54:01.877 回答
1

这是一个老问题，但无论如何，为了记录，这就是我在 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-06T16:01:09.297 回答
0

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

// 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-26T00:24:59.810 回答
0

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

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

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

顺便说一句，应该有 142,506 组 30 名学生组成一个 5 人组。我的 <sarcasm> 真棒</sarcasm> 数学技能表明应该有大约 10^17 = 100 千万个学生组的组合（ 30!/((5!^6)*6!); 30! 个学生的排序，6 组 5 的排序无关紧要，这 6 组的排序无关紧要）。你可能会坐在那里等待这个完成。

于 2009-10-26T01:55:44.200 回答