💼 Der perfekte Sitzplan: Das Leadership-Summit-Problem in Go gelöst 🔗

Die Organisation eines Führungskräfte-Gipfels oder einer großen Networking-Veranstaltung bringt eine ganz eigene logistische Herausforderung mit sich: Wie maximiert man die Interaktionen zwischen den Teilnehmern?

Wenn es mehrere Runden von Tischdiskussionen gibt, möchte man sicherstellen, dass die Teilnehmer ständig neue Gesichter kennenlernen. Idealerweise sollte niemand mit einer Person am selben Tisch sitzen, die er bereits in einer früheren Runde getroffen hat.

Diese Herausforderung ist ein klassisches kombinatorisches Rätsel (eng verwandt mit dem Social Golfer Problem). In diesem Beitrag untersuchen wir eine in Go geschriebene Backtracking-Lösung, die $N$ Tische mit jeweils $N$ Personen über maximal $(N + 1)$ Runden ohne doppelte Paarungen zuweisen kann.

📑 Inhaltsverzeichnis 🔗

📐 Die mathematische Grenze: Warum (N + 1) Runden? 🔗

Bevor wir in den Code eintauchen, bestimmen wir zunächst die absolute Höchstzahl an Runden, die wir planen können, bevor doppelte Paarungen mathematisch unvermeidbar werden.

Die maximale Anzahl an Runden beträgt $(N + 1)$.

Der Beweis: Stellen wir uns vor, wir haben $N$ Tische, und an jedem Tisch sitzen $N$ Personen. Das ergibt insgesamt $N \times N$ (oder $N^2$) Teilnehmer.

Betrachten wir die Veranstaltung nun aus der Perspektive eines einzelnen Teilnehmers, Person A:

1. In jeder Runde sitzt Person A mit $(N - 1)$ neuen Personen zusammen.
2. Die Gesamtzahl der anderen Teilnehmer auf der Veranstaltung, die Person A treffen kann, beträgt $(N^2 - 1)$.
3. Um herauszufinden, wie viele Runden nötig sind, damit Person A jeden genau einmal trifft, teilen wir die Gesamtzahl der verfügbaren Personen durch die Anzahl der Personen, die man pro Runde trifft:

Nach $(N + 1)$ Runden hat sich jeder Teilnehmer perfekt mit jedem anderen vernetzt.

🧠 Die algorithmische Strategie 🔗

Um dieses Problem effizient zu lösen, können wir einen Backtracking-Algorithmus verwenden. Um jedoch den Suchraum drastisch zu verkleinern und die Ausführung zu beschleunigen, können wir die ersten beiden Runden mit einem eleganten Trick fest vorgeben:

1. Runde 0 (Horizontal): Weise alle Teilnehmer der Reihe nach horizontal zu.
2. Runde 1 (Vertikal): Weise alle Teilnehmer der Reihe nach vertikal zu.
3. Verbleibende Runden: Nutze Backtracking, um jedem Platz eine gültige Permutation der Teilnehmer zuzuweisen und sicherzustellen, dass keine Sitzregeln verletzt werden.

💻 Implementierung in Go 🔗

Um den Fortschritt unseres Backtrackings zu verfolgen, verwenden wir ein State-Struct, das die aktuellen Tische, Runden sowie Maps speichert, die festhalten, wer bereits mit wem interagiert hat.

Hier ist die Kernlogik, aufgeteilt in drei Teile: die Suchschleife, die Konfliktprüfung und die Zustandsverwaltung.

🔍 1. Die Backtracking-Suche 🔗

Die Funktion solveImpl versucht rekursiv, dem nächsten freien Platz eine Person zuzuweisen. Führt ein Pfad zu einem Konflikt, macht sie den Schritt rückgängig (unset) und probiert die nächste Person aus.

func solveImpl(state *State) bool {
	if state.solved {
		return true
	}

	// For the first round, consider all people
	start := 0
	end := state.people

	// From the second round onwards, restrict the search space
	if len(state.res) > 0 {
		start = len(state.table) * state.tableSize
		end = start + state.tableSize
	}

	for person := start; person < end; person++ {
		if !valid(state, person) {
			continue // Skip if this assignment causes a conflict
		}
        
		set(state, person) // Assign the seat
		if solveImpl(state) {
			return true // Success!
		}
		unset(state, person) // Backtrack
	}
	
	return false
}

🛡️ 2. Konfliktprüfung 🔗

Eine Zuweisung ist ungültig (es liegt ein Konflikt vor), wenn:

1. Die Person in der aktuellen Runde bereits einem Platz zugewiesen wurde.
2. Die Person bereits in einer früheren Runde mit jemandem am selben Tisch saß, der aktuell an diesem Tisch sitzt.

func valid(state *State, person int) bool {
	// Has this person already been seated in this round?
	if state.usedPerson[person] {
		return false
	}
	
	// Has this person sat with anyone currently at this table before?
	for _, there := range state.table {
		first := min(there, person)
		second := max(there, person)
		
		if state.usedPair[first][second] {
			return false
		}
	}
	
	return true
}

⚙️ 3. Zustandsverwaltung (set und unset) 🔗

Wenn wir einer Person einen Platz zuweisen, müssen wir unseren Zustandstracker aktualisieren. Ist ein Tisch voll, wechseln wir zum nächsten. Ist eine Runde voll, gehen wir zur nächsten Runde über.

func set(state *State, person int) {
	state.usedPerson[person] = true
	
	// Mark this person as having paired with everyone currently at the table
	for _, there := range state.table {
		first := min(there, person)
		second := max(there, person)
		if _, ok := state.usedPair[first]; !ok {
			state.usedPair[first] = map[int]bool{}
		}
		state.usedPair[first][second] = true
	}
	
	state.table = append(state.table, person)
	
	// Move to next table if full
	if len(state.table) != state.tableSize {
		return
	}
	state.round = append(state.round, state.table)
	state.table = []int{}
	
	// Move to next round if all tables are full
	if len(state.round) != state.numTables {
		return
	}
	state.res = append(state.res, state.round)
	state.round = [][]int{}
	state.usedPeople = append(state.usedPeople, state.usedPerson)
	state.usedPerson = map[int]bool{}
	
	// Check if we are completely done
	if len(state.res) != state.numRounds {
		return
	}
	state.solved = true
}

Die Funktion unset ist das genaue Gegenstück und setzt den Zustand sorgfältig Schritt für Schritt zurück, wenn unser rekursiver Suchbaum in einer Sackgasse landet.

func unset(state *State, person int) {
	state.solved = false
	
	// If the current table is empty, step back to the previous table
	if len(state.table) == 0 {
		if len(state.round) == 0 {
			last := len(state.res) - 1
			state.round = state.res[last]
			state.res = state.res[:last]
			state.usedPerson = state.usedPeople[last]
			state.usedPeople = state.usedPeople[:last]
		}
		last := len(state.round) - 1
		state.table = state.round[last]
		state.round = state.round[:last]
	}
	
	// Remove the person from the table
	state.table = state.table[:len(state.table)-1]
	
	// Unmark pairings
	for _, there := range state.table {
		first := min(there, person)
		second := max(there, person)
		state.usedPair[first][second] = false
	}
	state.usedPerson[person] = false
}

📊 Die Ergebnisse 🔗

🔢 Beispiel: 4 Tische mit je 4 Personen (5 Runden) 🔗

Hier ist die Ausgabe für einen kleineren Gipfel mit $N=4$. Man sieht schön, wie die Zahlen in Runde 0 fortlaufend horizontal über die Tische verteilt sind und in Runde 1 vertikal durch die vorherigen Tische laufen.

round 0:
  table 0: 0  1  2  3
  table 1: 4  5  6  7
  table 2: 8  9  10 11
  table 3: 12 13 14 15

round 1:
  table 0: 0  4  8  12
  table 1: 1  5  9  13
  table 2: 2  6  10 14
  table 3: 3  7  11 15

round 2:
  table 0: 0  5  10 15
  table 1: 1  4  11 14
  table 2: 2  7  8  13
  table 3: 3  6  9  12

round 3:
  table 0: 0  6  11 13
  table 1: 1  7  10 12
  table 2: 2  4  9  15
  table 3: 3  5  8  14

round 4:
  table 0: 0  7  9  14
  table 1: 1  6  8  15
  table 2: 2  5  11 12
  table 3: 3  4  10 13

🚀 Skalierung: 8 Tische mit je 8 Personen (9 Runden) 🔗

Da wir unseren Suchbaum durch das Vorbefüllen der ersten beiden Runden intelligent beschneiden, skaliert der Algorithmus auch hervorragend für größere Gruppen. Unten findest du die Lösung für 64 Teilnehmer, verteilt auf 8 Tische.

round 0:
  table 0: 0  1  2  3  4  5  6  7
  table 1: 8  9  10 11 12 13 14 15
  table 2: 16 17 18 19 20 21 22 23
  table 3: 24 25 26 27 28 29 30 31
  table 4: 32 33 34 35 36 37 38 39
  table 5: 40 41 42 43 44 45 46 47
  table 6: 48 49 50 51 52 53 54 55
  table 7: 56 57 58 59 60 61 62 63

round 1:
  table 0: 0  8  16 24 32 40 48 56
  table 1: 1  9  17 25 33 41 49 57
  table 2: 2  10 18 26 34 42 50 58
  table 3: 3  11 19 27 35 43 51 59
  table 4: 4  12 20 28 36 44 52 60
  table 5: 5  13 21 29 37 45 53 61
  table 6: 6  14 22 30 38 46 54 62
  table 7: 7  15 23 31 39 47 55 63

round 2:
  table 0: 0  9  18 27 36 45 54 63
  table 1: 1  8  19 26 37 44 55 62
  table 2: 2  11 16 25 38 47 52 61
  table 3: 3  10 17 24 39 46 53 60
  table 4: 4  13 22 31 32 41 50 59
  table 5: 5  12 23 30 33 40 51 58
  table 6: 6  15 20 29 34 43 48 57
  table 7: 7  14 21 28 35 42 49 56

round 3:
  table 0: 0  10 20 30 35 41 55 61
  table 1: 1  11 21 31 34 40 54 60
  table 2: 2  8  22 28 33 43 53 63
  table 3: 3  9  23 29 32 42 52 62
  table 4: 4  14 16 26 39 45 51 57
  table 5: 5  15 17 27 38 44 50 56
  table 6: 6  12 18 24 37 47 49 59
  table 7: 7  13 19 25 36 46 48 58

round 4:
  table 0: 0  11 22 29 39 44 49 58
  table 1: 1  10 23 28 38 45 48 59
  table 2: 2  9  20 31 37 46 51 56
  table 3: 3  8  21 30 36 47 50 57
  table 4: 4  15 18 25 35 40 53 62
  table 5: 5  14 19 24 34 41 52 63
  table 6: 6  13 16 27 33 42 55 60
  table 7: 7  12 17 26 32 43 54 61

round 5:
  table 0: 0  12 19 31 38 42 53 57
  table 1: 1  13 18 30 39 43 52 56
  table 2: 2  14 17 29 36 40 55 59
  table 3: 3  15 16 28 37 41 54 58
  table 4: 4  8  23 27 34 46 49 61
  table 5: 5  9  22 26 35 47 48 60
  table 6: 6  10 21 25 32 44 51 63
  table 7: 7  11 20 24 33 45 50 62

round 6:
  table 0: 0  13 17 28 34 47 51 62
  table 1: 1  12 16 29 35 46 50 63
  table 2: 2  15 19 30 32 45 49 60
  table 3: 3  14 18 31 33 44 48 61
  table 4: 4  9  21 24 38 43 55 58
  table 5: 5  8  20 25 39 42 54 59
  table 6: 6  11 23 26 36 41 53 56
  table 7: 7  10 22 27 37 40 52 57

round 7:
  table 0: 0  14 23 25 37 43 50 60
  table 1: 1  15 22 24 36 42 51 61
  table 2: 2  12 21 27 39 41 48 62
  table 3: 3  13 20 26 38 40 49 63
  table 4: 4  10 19 29 33 47 54 56
  table 5: 5  11 18 28 32 46 55 57
  table 6: 6  8  17 31 35 45 52 58
  table 7: 7  9  16 30 34 44 53 59

round 8:
  table 0: 0  15 21 26 33 46 52 59
  table 1: 1  14 20 27 32 47 53 58
  table 2: 2  13 23 24 35 44 54 57
  table 3: 3  12 22 25 34 45 55 56
  table 4: 4  11 17 30 37 42 48 63
  table 5: 5  10 16 31 36 43 49 62
  table 6: 6  9  19 28 39 40 50 61
  table 7: 7  8  18 29 38 41 51 60

Wenn du das nächste Mal ein Networking-Event organisierst, spar dir die manuellen Tabellenkalkulationen und überlass die Schwerstarbeit einfach einem Backtracking-Algorithmus!