inteligentemente gerando combinações de combinações

Question

Vamos dizer que eu tenho uma classe de 30 alunos e quer gerar todas as formas possíveis em que eles podem ser divididos em grupos de 5 (a ordem é irrelevante).

Eu sei como encontrar todas as combinações de alunos para formar um grupo individualmente ( http: // www .merriampark.com / comb.htm ). Usando que iterador e alguns recursão, posso encontrar permutações das combinações possíveis do grupo. No entanto, a ordem em que os grupos são selecionados não é relevante e eu gostaria de minimizar o meu tempo de execução. Então, como faço para encontrar as combinações únicas de possíveis grupos?

O algoritmo acima usa ordenação lexicográfica para evitar a geração de combinações duplicadas ... existe uma maneira que eu posso usar essa idéia em grupos em vez de em objetos?

Eu sei rubi bem e Java / Python menos bem. Agradecemos antecipadamente por qualquer conselho!

Answer 1

Bem, há (30 _C 5 * 25 _C 5 * 20 _C 5 * 15 _C 5 * 10 _C 5 * 5 _C 5) / 6! = 30! / (6 * 5! ⁶ ) = 123,378,675,083,039,376 diferentes partitons de 30 em grupos de 5, assim gerando todos eles vai demorar algum tempo, não importa o método que você usa.

Em geral, porém, um método bom para selecionar uma partição deste tipo é usar algum ordenação dos elementos, e encontrar o agrupamento para o maior elemento não agrupada, e depois o resto do grupo.

     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]

Desta forma, você está gerando apenas uma vez cada partição

Answer 2

Esta é uma questão de idade, mas de qualquer maneira, para o registro, é assim que eu faria isso em 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

I usar um enumerador porque a saída pode crescer muito rapidamente, uma saída estrita (uma matriz, por exemplo) não seria útil. Um exemplo de uso:

>> 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

Você poderia fazer alguma pós-processamento nas permutações. Alguns pseudo-código (implementar na língua de sua escolha ...):

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

Provavelmente não o mais eficiente; Eu acrescentaria o tipo e comparar com o código que gera as permutações pessoalmente.

Answer 4

Uma possibilidade seria a de encontrar todas as combinações para formar um grupo individual, em seguida, passar e gerar combinações que não contêm membros desse grupo individual. Algo como:

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

Não vai ser o método mais eficiente de fazê-lo, mas deve gerar todas as combinações de grupos. Eu suspeito melhor desempenho poderia ser tido, se você fosse para gerar listas provisórias de combinações, onde em todos os grupos que não podem ocorrer foram removidos, mas que seria um pouco mais complexa.

Como um ligeiro de lado, deve haver 142,506 combinações de 30 alunos para formar um único grupo de 5. Meu incrível habilidades matemáticas sugerem que deve haver cerca de 10 ^ 17 = 100 combinações quatrilhão de grupos (! 30 / ((5 ^ 6) * 6)!; 30 ordenações de estudantes, ordenação dos 6 grupos de 5 não importa, e ordenação dos 6 grupos não importa) dos estudantes. Você pode estar sentado lá um tempo esperando por este ao fim.