générer intelligemment des combinaisons de combinaisons

Question

Disons que j'ai une classe de 30 étudiants et que je veux générer toutes les façons possibles de les partitionner en groupes de 5 (l'ordre n'est pas pertinent). Je sais comment trouver toutes les combinaisons d'étudiants pour former un groupe individuellement (http://www.merriampark.com/comb.htm). En utilisant cet itérateur et une certaine récursivité, je peux trouver des PERMUTATIONS des combinaisons de groupes possibles. Cependant, l'ordre dans lequel les groupes sont sélectionnés n'est pas pertinent et j'aimerais minimiser mon temps d'exécution. Alors, comment puis-je trouver les COMBINAISONS uniques des groupes possibles? L'algorithme ci-dessus utilise l'ordre lexicographique pour éviter de générer des combinaisons en double ... est-ce que je peux utiliser cette idée sur des groupes plutôt que sur des objets?

Je connais moins bien Ruby et Java/Python. Merci d'avance pour tout conseil!

Answer 1

Eh bien, il y a (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 différentes parties de 30 en groupes de 5, donc les générer tous prendra un certain temps, peu importe la méthode que vous utilisez. En général, cependant, une bonne méthode pour sélectionner une telle partition consiste à utiliser un ordre sur les éléments, à trouver le regroupement pour l'élément le plus élevé non groupé, puis à regrouper le reste.

 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] 

De cette façon, vous ne générer chaque partition une fois

Answer 2

Vous pouvez effectuer un post-traitement sur les permutations. Certains pseudo-code (mettre en œuvre dans la langue de votre choix ...):

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

Probablement pas le plus efficace; Je voudrais ajouter le type & comparer au code qui génère les permutations personnellement.

Answer 3

Une possibilité serait de trouver toutes les combinaisons pour former un groupe individuel, puis de passer et de générer des combinaisons qui ne contiennent pas de membres de ce groupe individuel. Quelque chose comme:

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

Ce ne sera pas la méthode la plus efficace pour y arriver, mais elle devrait générer toutes les combinaisons de groupes. Je soupçonne que de meilleures performances pourraient être obtenues si vous deviez générer des listes temporaires de combinaisons, où tous les groupes qui ne peuvent pas apparaître ont été supprimés, mais cela serait un peu plus complexe.

Comme une légère part, il devrait y avoir 142,506 combinaisons de 30 étudiants pour former un seul groupe de 5. Mon <sarcasme> impressionnant </sarcasme > compétences en mathématiques suggèrent qu'il devrait y avoir environ 10^17 = 100 quadrillions combinaisons de groupes d'étudiants (30!/((5!^6) * 6!); 30! commandes d'étudiants, l'ordre de 6 groupes de 5 n'a pas d'importance, et l'ordre de ces 6 groupes n'a pas d'importance). Vous pourriez être assis là un moment en attendant que cela se termine.

Answer 4

C'est une vieille question, mais de toute façon, pour l'enregistrement, c'est comment je en 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 utilisez un énumérateur car la sortie peut se développer très rapidement, une sortie stricte (un tableau par exemple) ne serait pas utile. Un exemple d'utilisation:

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