💼 La Disposizione dei Posti Perfetta: Risolvere il Problema del Leadership Summit in Go 🔗

Organizzare un leadership summit o un evento di networking su larga scala comporta un grattacapo logistico unico: come massimizzare le interazioni tra i partecipanti?

Se sono previsti più turni di discussioni ai tavoli, vuoi assicurarti che le persone incontrino costantemente volti nuovi. Idealmente, nessuna persona dovrebbe sedersi allo stesso tavolo con qualcuno che ha già incontrato in un turno precedente.

Questa sfida è un classico rompicapo di calcolo combinatorio (strettamente legato al Social Golfer Problem). In questo articolo esploreremo una soluzione basata sul backtracking scritta in Go, in grado di assegnare $N$ tavoli con $N$ persone ciascuno, per un massimo di $(N + 1)$ turni, senza alcuna coppia duplicata.

📑 Indice 🔗

📐 Il Limite Matematico: Perché (N + 1) Turni? 🔗

Prima di immergerci nel codice, stabiliamo il numero massimo assoluto di turni che possiamo programmare prima che le coppie duplicate diventino matematicamente inevitabili.

Il numero massimo di turni è $(N + 1)$.

La Dimostrazione: Immaginiamo di avere $N$ tavoli, e che ogni tavolo ospiti $N$ persone. Questo ci dà un totale di $N \times N$ (ovvero $N^2$) partecipanti.

Ora, osserviamo l’evento dal punto di vista di un singolo partecipante, la Persona A.

1. In ogni turno, la Persona A si siede con $(N - 1)$ nuove persone.
2. Il numero totale di altre persone presenti all’evento che la Persona A può incontrare è $(N^2 - 1)$.
3. Per scoprire quanti turni servono affinché la Persona A incontri tutti esattamente una volta, dividiamo il totale delle persone disponibili per il numero di persone incontrate a ogni turno:

Dopo $(N + 1)$ turni, ciascuno avrà fatto networking perfetto con tutti gli altri.

🧠 La Strategia Algoritmica 🔗

Per risolvere questo problema in modo efficiente, possiamo usare un algoritmo di backtracking. Tuttavia, per ridurre drasticamente lo spazio di ricerca e velocizzare l’esecuzione, possiamo preimpostare i primi due turni usando un trucco elegante:

1. Turno 0 (Orizzontale): Assegna tutti in ordine sequenziale orizzontalmente.
2. Turno 1 (Verticale): Assegna tutti in ordine sequenziale verticalmente.
3. Turni Rimanenti: Usa il backtracking per assegnare a ogni posto una permutazione valida dei partecipanti, assicurandoti che nessuna regola di disposizione venga violata.

💻 Implementazione in Go 🔗

Per tenere traccia dei progressi del nostro backtracking, utilizziamo una struct State che conserva i tavoli correnti, i turni e le mappe per tracciare chi ha interagito con chi.

Ecco la logica principale suddivisa in tre parti: il ciclo di ricerca, la validazione dei conflitti e la gestione dello stato.

🔍 1. La Ricerca con Backtracking 🔗

La funzione solveImpl prova ricorsivamente ad assegnare una persona al prossimo posto disponibile. Se un percorso porta a un conflitto, torna indietro (unset) e prova con la persona successiva.

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. Validazione dei Conflitti 🔗

Un’assegnazione non è valida (si verifica un conflitto) se:

1. Alla persona è già stato assegnato un posto nel turno corrente.
2. La persona si è già seduta in un turno precedente con qualcuno attualmente presente al tavolo.

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. Gestione dello Stato (set e unset) 🔗

Quando assegniamo una persona a un posto, dobbiamo aggiornare il nostro tracciatore di stato. Se un tavolo si riempie, passiamo al successivo. Se un turno si completa, passiamo al turno successivo.

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 funzione unset è l’esatto inverso, e riporta attentamente indietro lo stato quando il nostro albero ricorsivo raggiunge un vicolo cieco.

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
}

📊 I Risultati 🔗

🔢 Esempio: 4 Tavoli, 4 Persone Ciascuno (5 Turni) 🔗

Ecco l’output per un summit più piccolo con $N=4$. Nota come nel Turno 0 i numeri procedano in sequenza lungo i tavoli, mentre nel Turno 1 procedano in sequenza verticalmente rispetto ai tavoli precedenti.

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

🚀 Scalare: 8 Tavoli, 8 Persone Ciascuno (9 Turni) 🔗

Poiché potiamo il nostro albero di ricerca in modo intelligente precompilando i primi due turni, l’algoritmo scala egregiamente anche per gruppi più numerosi. Qui sotto trovi la soluzione per 64 partecipanti distribuiti su 8 tavoli.

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 prossima volta che dovrai organizzare un evento di networking, lascia perdere i fogli di calcolo manuali e lascia che sia un algoritmo di backtracking a fare il lavoro pesante per te!