智能地生成组合的组合

StackOverflow https://stackoverflow.com/questions/1622574

  •  06-07-2019
  •  | 
  •  

题

假设我有一个30个学生的班级，并希望生成一种可能的方式，将它们划分为5个组（顺序无关紧要）。

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

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

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

有帮助吗？

解决方案

嗯，有（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]

这样你只需要生成一次分区

其他提示

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

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

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

可能不是最有效的;我要添加排序<！>放大器;与个人生成排列的代码进行比较。

一种可能性是找到所有组合以形成单个组，然后通过并生成不包含该组个体成员的组合。类似的东西：

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名学生的142,506个组合形成一组5.我的<！> lt; sarcasm <！> gt;真棒<！> lt; / sarcasm <！> gt;数学技能表明应该有大约10 ^ 17 = 100千万亿组的学生组合（30！/（（5！^ 6）* 6！）; 30！学生的排序，6组5的排序无关紧要，这6组的订购无关紧要）。你可能会坐在那里等待完成。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top