intelligente Kombinationen von Kombinationen zu erzeugen

Question

Lassen Sie uns sagen, dass ich eine Klasse von 30 Schülern haben und jede erdenkliche Art und Weise erzeugt werden soll, in denen sie in Gruppen von 5 aufgeteilt werden (Reihenfolge spielt keine Rolle).

Ich weiß, wie alle Kombinationen von Studenten zu finden, individuell eine Gruppe zu bilden ( http: // www .merriampark.com / comb.htm ). Durch die Verwendung dieses Iterator und einig Rekursion, kann ich Permutationen der möglichen Gruppenkombinationen finden. Allerdings Reihenfolge, in der die Gruppen ausgewählt werden, ist nicht relevant, und ich möchte meine Ausführungszeit minimieren. So wie ich die einzigartige Kombination der möglichen Gruppen finden?

Der obige Algorithmus verwendet lexikographische Ordnung doppelte Kombinationen zu vermeiden Erzeugung ... Gibt es eine Möglichkeit, dass ich diese Idee auf Gruppen verwenden kann, anstatt auf Objekte?

Ich weiß, Rubin gut und Java / Python weniger gut. Vielen Dank im Voraus für jede Beratung!

Answer 1

Nun, es gibt (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 unterschiedliche partitons von 30 in Gruppen von 5, so zu erzeugen, sie alle werden einige Zeit dauern, egal, welche Methode Sie verwenden.

In der Regel aber eine gute Methode, eine solche Partition um die Auswahl ist etwas Ordnung auf den Elementen zu verwenden, und die Gruppierung für die höchste ungruppierten Element zu finden, und dann die Gruppe der Rest.

     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]

Auf diese Weise Sie nur jede Partition einmal zu erzeugen

Answer 2

Dies ist eine alte Frage, aber wie auch immer, für die Aufzeichnung, das ist, wie ich würde es in 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

ich einen Enumerator verwenden, weil der Ausgang sehr schnell wachsen kann, ein strikter Ausgang (ein Array zum Beispiel) wäre nicht sinnvoll sein. Ein Anwendungsbeispiel:

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

Sie könnten einige Nachbearbeitung auf den Permutationen tun. Einige Pseudo-Code (implementieren in der Sprache Ihrer Wahl ...):

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

Wahrscheinlich nicht die effizienteste; Ich würde die Art hinzuzufügen und zu dem Code zu vergleichen, die persönlich die Permutationen erzeugt.

Answer 4

Eine Möglichkeit wäre, alle Kombinationen zu finden, eine einzelne Gruppe zu bilden, dann gehen Sie durch und generieren Kombinationen, die nicht Mitglieder dieser einzelnen Gruppe enthalten. So etwas wie:

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

Es wird die effizienteste Methode zu gehen, um es nicht, aber es sollte alle Kombinationen von Gruppen erzeugen. Ich vermute, eine bessere Leistung zu haben war, wenn Sie temporäre Listen von Kombinationen zu erzeugen sind, wo in allen Gruppen, die nicht entfernt wurden auftreten können, aber das wäre ein wenig komplexer sein.

Wie ein leichter beiseite, sollte es 142.506 Kombinationen von 30 Studenten sein, eine einzelne Gruppe von 5. Mein bilden genial mathematische Fähigkeiten deuten darauf hin, dass es etwa 10 ^ 17 = 100 Billi Kombinationen von Gruppen sein die Studierenden (30 / ((5 ^ 6) * 6);!!! 30 Ordnungen von Studenten, die Bestellung von 6 Gruppen von 5 keine Rolle spielen, und Bestellung von diesen sechs Gruppen spielt keine Rolle). Man könnte es eine Weile sitzen warten auf diese zu beenden.