智能地产生组合的组合(intelligently generating combinations o

2019-09-01 04:19发布

比方说,我有一个班的30名学生,并希望生成,使他们能够(顺序无关)分成5组无微不至。

我知道如何找到学生的所有组合,形成一组可独立( http://www.merriampark.com/comb.htm )。 通过使用迭代器和一些递归,我可以找到可能的组组合排列。 然而,在该组选定的顺序是不相关的,我想,以尽量减少我的执行时间。 那么,如何寻找可能的组的唯一组合?

上述算法使用字典序,以避免产生重复的组合...有,我可以使用组而不是对对象思想的方式?

我知道红宝石以及和Java / Python的较差。 在此先感谢您的任何建议!

Answer 1:

嗯,有(30℃5 * 25℃5 * 20℃5 * 15℃5 * 10℃5 * 5 C 5)/ 6! = 30!/(6!* 5!6)= 30 123,378,675,083,039,376不同partitons成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名学生142506个组合以形成5我<讽刺>的单组真棒</讽刺>数学技能建议应该是大约10 ^ 17 = 100个万亿学生的基团的组合( !30 /(!(5 ^ 6)* 6!!); 30名学生的排序,6组5的顺序并不重要,和那些6组的顺序并不重要)。 你可能会坐在那里等待此完成。



文章来源: intelligently generating combinations of combinations