générer intelligemment des combinaisons de combinaisons

Question

Supposons que j'ai une classe de 30 étudiants et que je souhaite générer tous les moyens possibles de les diviser en groupes de 5 (l'ordre est indifférent).

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écursion, 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. Y a-t-il moyen de pouvoir utiliser cette idée sur des groupes plutôt que sur des objets?

Je connais bien Ruby et Java / Python moins bien. 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 parties différentes de 30 en groupes de 5, afin de toutes les générer prendra un certain temps, quelle que soit 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 de tri des éléments, à rechercher le regroupement de l'élément non groupé le plus élevé, puis à grouper 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]

Ainsi, vous ne générez qu'une seule fois chaque partition

Answer 2

C’est une vieille question, mais de toute façon, pour mémoire, c’est comme ça que je le ferais dans 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

J'utilise un énumérateur car la sortie peut croître 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]]]

Answer 3

Vous pouvez faire du post-traitement sur les permutations. Quelques pseudo-codes (à implémenter 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; J'ajouterais le genre & Amp; comparer au code qui génère les permutations personnellement.

Answer 4

Une possibilité serait de trouver toutes les combinaisons pour former un groupe individuel, puis de passer à travers 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, mais elle devrait générer toutes les combinaisons de groupes. Je suppose que de meilleures performances pourraient être obtenues si vous deviez générer des listes temporaires de combinaisons, dans lesquelles tous les groupes qui ne pouvaient pas se produire étaient supprimés, mais cela serait un peu plus complexe.

En passant, il devrait y avoir 142 506 combinaisons de 30 étudiants pour former un seul groupe de 5. Mon < sarcasme > génial < / sarcasme > compétences en mathématiques suggèrent qu'il devrait y avoir environ 10 ^ 17 = 100 quadrillions de combinaisons de groupes d'élèves (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 êtes peut-être assis un moment à attendre que cela se termine.