Ein Freund von mir, der Lehrer ist, hat 23 Schüler in einer Klasse. Sie wollen einen Algorithmus, der Schülern in Gruppen von 2 und einer Gruppe von 3 (mit der ungeraden Anzahl von Schülern) über 14 Wochen so zuweist, dass sich keine zwei Paare über die 14 Wochen wiederholen (ein Paar ist einer Woche zugeordnet).
Round-Robin-Algorithmus wird den Trick machen, den ich denke.
Fügen Sie den verbleibenden Schüler der zweiten Gruppe hinzu und Sie sind fertig.
%Vor%...
Eine andere Möglichkeit könnte Graphenabgleich sein, 14 verschiedene Graph-Matchings wären erforderlich.
Hier ist ein Beispiel in Haskell, das Gruppen von 14 sich nicht wiederholenden 11-Paar-Kombinationen erzeugt. Der Wert "Paare" ist eine Kombination von Paaren von 1 bis 23 (z. B. [1,2], [1,3] usw.). Dann erstellt das Programm Listen, in denen jede Liste 14 Listen mit 11 Paaren ist (Auswahl aus dem Wert "Paare"), so dass kein Paar wiederholt wird und keine einzelne Zahl in einer Liste von 11 Paaren wiederholt wird. Es liegt an Ihnen, den fehlenden letzten Schüler für jede Woche einfach so zu platzieren, wie Sie es für richtig halten. (Es hat ungefähr drei Minuten gedauert, bis die Ergebnisse ausgegeben wurden):
%Vor%Ein Beispiel aus der Ausgabe:
%Vor%Beginnen Sie mit einem Set (vielleicht ein Bitset-Mapping für weniger Speicherverbrauch für Schüler) für jeden Schüler, der alle anderen Schüler darin hat. Iterate 14 Mal, jedes Mal, wenn du 11 Schüler auswählst (für die 11 Gruppen, die du bilden wirst), für die du Partner auswählst. Wählen Sie für jeden Schüler einen Partner, mit dem sie noch nicht in einer Gruppe waren. Für einen zufälligen Schüler dieser 11 wählen Sie einen zweiten Partner, aber stellen Sie sicher, dass kein Schüler weniger verbleibende Partner hat, als Iterationen übrig sind. Passen Sie die Sätze für jede Auswahl an.
Tags und Links algorithm combinatorics