💼 Le plan de table parfait : résoudre le problème du sommet de leadership en Go 🔗

Organiser un sommet de leadership ou un événement de réseautage à grande échelle s’accompagne d’un casse-tête logistique particulier : comment maximiser les interactions entre les participants ?

Si vous organisez plusieurs tours de discussions à table, vous voulez vous assurer que les participants rencontrent constamment de nouveaux visages. Idéalement, personne ne devrait s’asseoir à la même table qu’une personne déjà rencontrée lors d’un tour précédent.

Ce défi est un casse-tête combinatoire classique (étroitement lié au problème des golfeurs ou Social Golfer Problem). Dans cet article, nous allons explorer une solution par retour sur trace (backtracking) écrite en Go, capable d’assigner $N$ tables de $N$ personnes chacune, pour un maximum de $(N + 1)$ tours, sans aucune paire en doublon.

📑 Table des Matières 🔗

📐 La borne mathématique : pourquoi (N + 1) tours ? 🔗

Avant de plonger dans le code, établissons le nombre maximum absolu de tours que nous pouvons programmer avant que les paires en doublon ne deviennent mathématiquement inévitables.

Le nombre maximum de tours est $(N + 1)$.

La démonstration : Imaginons que nous ayons $N$ tables, et que chaque table accueille $N$ personnes. Cela nous donne un total de $N \times N$ (soit $N^2$) participants.

Examinons maintenant l’événement du point de vue d’un seul participant, la Personne A.

1. À chaque tour, la Personne A s’assoit avec $(N - 1)$ nouvelles personnes.
2. Le nombre total d’autres personnes présentes à l’événement que la Personne A peut rencontrer est de $(N^2 - 1)$.
3. Pour savoir combien de tours il faut à la Personne A pour rencontrer tout le monde exactement une fois, nous divisons le nombre total de personnes disponibles par le nombre de personnes rencontrées par tour :

Après $(N + 1)$ tours, tout le monde aura parfaitement échangé avec tout le monde.

🧠 La stratégie algorithmique 🔗

Pour résoudre ce problème efficacement, nous pouvons utiliser un algorithme de backtracking (retour sur trace). Cependant, pour réduire drastiquement l’espace de recherche et accélérer l’exécution, nous pouvons coder en dur les deux premiers tours grâce à une astuce élégante :

1. Tour 0 (Horizontal) : Assigner tout le monde dans l’ordre séquentiel horizontalement.
2. Tour 1 (Vertical) : Assigner tout le monde dans l’ordre séquentiel verticalement.
3. Tours restants : Utiliser le backtracking pour attribuer à chaque siège une permutation valide des participants, en veillant à ce qu’aucune règle de placement ne soit enfreinte.

💻 Implémentation en Go 🔗

Pour suivre la progression de notre backtracking, nous utilisons une structure State qui conserve les tables actuelles, les tours et des dictionnaires (map) permettant de suivre qui a interagi avec qui.

Voici la logique principale décomposée en trois parties : la boucle de recherche, la validation des conflits et la gestion de l’état.

🔍 1. La recherche par backtracking 🔗

La fonction solveImpl tente récursivement d’assigner une personne au prochain siège disponible. Si un chemin entraîne un conflit, elle revient en arrière (unset) et essaie la personne suivante.

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. Validation des conflits 🔗

Une attribution est invalide (un conflit survient) si :

1. La personne s’est déjà vu attribuer un siège au cours du tour actuel.
2. La personne s’est déjà assise avec quelqu’un actuellement présent à la table lors d’un tour précédent.

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. Gestion de l’état (set et unset) 🔗

Lorsque nous attribuons un siège à une personne, nous devons mettre à jour notre suivi d’état. Si une table se remplit, nous passons à la suivante. Si un tour est complet, nous passons au tour suivant.

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
}

La fonction unset est l’exact opposé, annulant soigneusement l’état lorsque notre arbre récursif aboutit à une impasse.

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
}

📊 Les résultats 🔗

🔢 Exemple : 4 tables, 4 personnes par table (5 tours) 🔗

Voici le résultat pour un petit sommet avec $N=4$. Remarquez comment au Tour 0, les numéros se suivent horizontalement d’une table à l’autre, et au Tour 1, ils se suivent verticalement à partir des tables précédentes.

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

🚀 Passage à l’échelle : 8 tables, 8 personnes par table (9 tours) 🔗

Parce que nous élaguons notre arbre de recherche intelligemment en pré-remplissant les deux premiers tours, l’algorithme passe très bien à l’échelle pour des groupes plus importants. Voici la solution pour 64 participants répartis sur 8 tables.

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

La prochaine fois que vous devrez organiser un événement de réseautage, oubliez les feuilles de calcul manuelles et laissez un algorithme de backtracking faire le gros du travail pour vous !