💼 O Mapa de Assentos Perfeito: Resolvendo o Problema do Encontro de Liderança em Go 🔗

Organizar um encontro de liderança ou um evento de networking em grande escala traz uma dor de cabeça logística única: como maximizar as interações entre os participantes?

Se você tiver várias rodadas de discussões em mesas, vai querer garantir que as pessoas estejam constantemente conhecendo rostos novos. Idealmente, nenhuma pessoa deveria se sentar à mesma mesa que alguém que já conheceu em uma rodada anterior.

Esse desafio é um quebra-cabeça clássico de combinatória (intimamente relacionado ao Social Golfer Problem). Neste post, exploraremos uma solução de backtracking escrita em Go capaz de alocar $N$ mesas com $N$ pessoas cada, por um máximo de $(N + 1)$ rodadas, sem repetir nenhum par de participantes.

📑 Índice 🔗

📐 O Limite Matemático: Por Que (N + 1) Rodadas? 🔗

Antes de mergulhar no código, vamos estabelecer o número máximo absoluto de rodadas que podemos agendar antes que pares duplicados se tornem matematicamente inevitáveis.

O número máximo de rodadas é $(N + 1)$.

A Demonstração: Imagine que temos $N$ mesas, e cada mesa acomoda $N$ pessoas. Isso nos dá um total de $N \times N$ (ou $N^2$) participantes.

Agora, observe o evento sob a perspectiva de um único participante, a Pessoa A.

1. Em cada rodada, a Pessoa A se senta com $(N - 1)$ novas pessoas.
2. O número total de outras pessoas no evento para a Pessoa A conhecer é $(N^2 - 1)$.
3. Para descobrir quantas rodadas são necessárias para a Pessoa A conhecer todo mundo exatamente uma vez, dividimos o total de pessoas disponíveis pelo número de pessoas conhecidas por rodada:

Após $(N + 1)$ rodadas, todos terão feito networking perfeitamente com todos os outros.

🧠 A Estratégia Algorítmica 🔗

Para resolver isso de forma eficiente, podemos usar um algoritmo de backtracking. No entanto, para reduzir drasticamente o espaço de busca e acelerar a execução, podemos fixar as duas primeiras rodadas usando um truque simples:

1. Rodada 0 (Horizontal): Alocar todos em ordem sequencial horizontalmente.
2. Rodada 1 (Vertical): Alocar todos em ordem sequencial verticalmente.
3. Rodadas Restantes: Usar backtracking para atribuir a cada assento uma permutação válida dos participantes, garantindo que nenhuma regra de alocação seja quebrada.

💻 Implementação em Go 🔗

Para acompanhar o progresso do nosso backtracking, usamos uma struct State que armazena as mesas atuais, as rodadas e mapas para rastrear quem já interagiu com quem.

Aqui está a lógica central dividida em três partes: o loop de busca, a validação de conflitos e o gerenciamento de estado.

🔍 1. A Busca por Backtracking 🔗

A função solveImpl tenta atribuir recursivamente uma pessoa ao próximo assento disponível. Se um caminho resultar em conflito, ela retrocede (unset) e tenta a próxima pessoa.

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. Validação de Conflitos 🔗

Uma atribuição é inválida (ocorre um conflito) se:

1. A pessoa já recebeu um assento na rodada atual.
2. A pessoa já se sentou em uma rodada anterior com alguém que está atualmente na mesa.

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. Gerenciamento de Estado (set e unset) 🔗

Quando atribuímos uma pessoa a um assento, precisamos atualizar nosso rastreador de estado. Se uma mesa encher, passamos para a próxima. Se uma rodada encher, passamos para a próxima rodada.

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
}

A função unset é o inverso exato, revertendo cuidadosamente o estado quando nossa árvore recursiva chega a um beco sem saída.

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
}

📊 Os Resultados 🔗

🔢 Exemplo: 4 Mesas, 4 Pessoas Cada (5 Rodadas) 🔗

Aqui está a saída para um encontro menor com $N=4$. Observe como na Rodada 0 os números seguem sequencialmente pelas mesas e, na Rodada 1, descem sequencialmente pelas mesas anteriores.

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

🚀 Escalando: 8 Mesas, 8 Pessoas Cada (9 Rodadas) 🔗

Como podamos nossa árvore de busca de forma inteligente ao preencher previamente as duas primeiras rodadas, o algoritmo escala muito bem para grupos maiores. Abaixo está a solução para 64 participantes distribuídos em 8 mesas.

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

Na próxima vez que você precisar organizar um evento de networking, deixe as planilhas manuais de lado e coloque um algoritmo de backtracking para fazer o trabalho pesado por você!