Ich habe gestern Nacht eine Real-Life-Aufgabe von einem Bekannten bekommen und bin noch nicht sicher, ob mein Ansatz sinnvoll ist.
Aufgabe:
Es gibt ein großes Kennenlern-Seminar mit 4 Runden (Touren). Das Seminar hat x Räume und y Teilnehmer. Nun ist es Aufgabe, die Teilnehmer so je Runde in den Räumen zu verteilen, dass sich so viele Leute wie möglich miteinander treffen - bzw. anders gesagt, sich jeder Teilnehmer bestmöglich mit allen anderen Teilnehmern einmal sieht.
Mein Ansatz
Ich habe versucht, es erst mal einfach mit 3 Räumen A, B, C und 9 Personen anzugehen:
Runde 1 (einfach der Personennummer nacheinander aufgeteilt):
Für die nächsten Runden darf also Person 1 nicht mehr Personen 2 und 3 begegnen. Bestmöglich.
Runde 2 horizontale Verschiebungen I
Ich verschiebe die Indexe für die 2. horizontale Reihe um +1 und für die 3. Reihe um +2:
Runde 3 horizontale Verschiebungen II
Ich verschiebe erneut die Indexe für die 2. horizontale Reihe um +1 und für die 3. Reihe um +2:
Eine weitere horizontale Verschiebung ist jetzt nicht mehr möglich, sonst würden sich Teilnehmer erneut sehen.
Runde 4 - Horizontal zu Vertikal
Person 1 war noch nicht mit Person 4 und Person 7 in einem Zimmer - drehen wir horizontal also zu vertikal:
So scheint es also in einfachster Weise zu klappen.
Meine Aufgabe ist es, hierfür einen sinnvollen "Algorithmus" zu finden - oder besser: direkt in ein Programm umzusetzen, wie gesagt, mit beliebig vielen x Räumen und y Teilnehmern. Und hier liegt der Knackpunkt, die Index-Verschiebung (neue Positionen je Runde) sollte kein Problem sein, aber kann ich bspw. diese Drehung von Horizontal zu Vertikal immer durchführen, ohne auf Probleme zu stoßen?
Nebenbei wird es noch eine Nummer schwieriger, wenn wir die Anzahl an Teilnehmern je Raum anders festlegen ... aber das für später. Erst mal ist das obige zu verstehen und eine allgemeine Lösung zu finden.
Danke vorab für eure Ansätze und Ideen!
Kai
PS: Aufgabe erinnert irgendwie an Kombinatorik und Matrizen ...
