Bons arranjos de assentos para sequência de refeições e mesas de tamanho k para um grupo de pessoas

Dado um conjunto de pessoas que eu gostaria de sentar-los para uma seqüência de refeições em mesas de tamanho k . (É claro que existem mesas suficientes para acomodar todos | S | para cada refeição.) Gostaria de organizar isso de modo que ninguém compartilhe uma mesa com a mesma pessoa duas vezes. Valores típicos são | S | = 45 e k = 5 e 6 a 10 refeições.$S$$k$$|S|$$|S|=45$$k=5$

Em termos mais abstratos, eu gostaria de encontrar uma sequência de partições de modo que cada partição consista em subconjuntos de cardinalidade k separados por pares e na propriedade global adicionada de que qualquer interseção entre dois desses subconjuntos não contém mais de um elemento. Suspeito que isso possa ser formulado como um problema teórico ou combinatório de gráfico.$S$$k$

Ficaria grato por uma melhor formulação do problema e indicadores para a literatura relevante, pois ela está fora do meu domínio.

Antecedentes: isso poderia ser usado para arranjos de assentos na Schloss Dagstuhl, onde muitos cientistas da computação vêm discutir suas pesquisas ao longo de uma semana. Atualmente, os assentos são feitos aleatoriamente e sem surpresa algumas pessoas se veem sentadas com as mesmas pessoas duas vezes (ou mais frequentemente) ao longo de uma semana. Também sem surpresa, recebemos algumas reclamações sobre isso e sugestões vagas de como melhorar isso. Eu gostaria de entender isso melhor. Uma formulação mais forte do problema envolve otimizar quem está sentado um ao lado do outro, mas acredito que isso não é relevante para tabelas de tamanho 5.

Fora da aplicação, acho que a pergunta interessante é o número máximo de refeições que podem ser servidas para um dado e k , ou seja, quantas dessas partições existem.$S$$k$

Aqui está uma variante da resposta original (abaixo) que fornece a configuração desejada: tabelas de tamanho 5, 45 pessoas e 10 refeições, exceto que uma refeição possui algumas tabelas de tamanho 4.

Seja o campo do tamanho 9. Escolha 4 linhas verticais e degeneradas { ( b , x ) | x ∈ F } para cada b = 0 , 1 , 2 , 3 e declara seu povo "vazio". Ficamos com 81 - 9x4 = 45 pessoas.$F$$\{(b,x) | x \in F\}$$b = 0,1,2,3$

9 refeições são dadas pelas pistas . As interseções com as quatro linhas degeneradas vazias reduzem o tamanho da tabela para 9-4 = 5.$a = 0,1,\ldots,8$

Uma refeição adicional é dada pelas linhas degeneradas restantes para cada b = 4 , 5 , 6 , 7 , 8 . Aqui o tamanho da tabela é 9. No entanto (em qualquer solução), podemos dividir uma tabela do tamanho 9 em uma tabela do tamanho 5 e uma do tamanho 4.$\{(b,x) | x \in F\}$$b = 4,5,6,7,8$

Se houver mais algumas pessoas, pode-se usar o campo de tamanho 11.

Primeiro vamos lidar com pessoas e k refeições.$k^2$$k$

Escolha um campo finito de tamanho k e identificar as pessoas com F × F . Para cada refeição corresponde uma inclinação, para uma tabela uma linha paralela a essa inclinação.$F$$k$$F \times F$

Especificamente, a refeição possui k tabelas { ( x , a x + b ) | x ∈ F } para cada b ∈ F .$a$$k$$\{(x,ax+b) | x \in F\}$$b \in F$

A propriedade de interseção que você deseja é o fato de que linhas com inclinações distintas se cruzam exatamente em um ponto.

Para lidar com pessoas, divida-as em dois grupos de k 2 cada e aplique a construção acima a cada grupo. Para manipular 2 k 2 - k = 45 , rotule (no primeiro grupo) uma linha fixa como { ( x , x ) | x ∈ F } como "vazio". Você pode ter algumas mesas com k - 1 pessoas.$2k^2$$k^2$$2k^2 - k = 45$$\{(x,x)|x\in F\}$$k-1$

Para mais refeições, pode-se, por exemplo, escolher uma partição diferente em dois grupos no início da 6ª refeição. (Digamos que intercale a partição original, para garantir que os dois grupos se misturem.) Embora, é claro, isso possa resultar em algumas interseções.

Aqui está um limite superior (flexível) do número de refeições que você pode servir.

$|S| = n$$n$$k$$n/k$

$S$$n/k$$k$$\Theta(nk)$

$n$$\Theta(n^2)$$O(n/k)$

$\frac{n-1}{k-1}$

Se você deseja que duas pessoas se sentem na mesma mesa exatamente uma vez, isso é chamado de projeto 2 resolvível e foi muito estudado. É claro que permitir pular algumas refeições daria uma solução para o seu problema quando duas pessoas podem se encontrar ao mesmo tempo. (Mas outras soluções podem existir, suponho.)

Não sei se você precisa de um algoritmo determinístico, mas resolvi um problema semelhante no passado usando o método Monte Carlo da cadeia de Markov .

Você pode ver um exemplo prático dessa abordagem no Github - este programa tenta acomodar um grupo de pessoas em mesas de tamanho fixo, considerando um conjunto de restrições de assentos que podem ser positivas ou negativas ("must" ou "must not" ) e absoluto ou relativo ("preferível").

Nota: este programa não resolve exatamente o mesmo problema que você propõe, mas fornece uma demonstração funcional do método Monte Carlo da cadeia de Markov, e está perto o suficiente para que você possa ajustá-lo facilmente conforme necessário para o seu problema.

O programa resolve o problema para um jantar, mas no seu caso, uma maneira fácil de abordar o problema seria executar o algoritmo uma vez para cada jantar, sempre fornecendo aos companheiros anteriores de cada restaurante como requisitos negativos nebulosos ou absolutos. (A vantagem dos requisitos nebulosos é que você garante que o algoritmo será interrompido em todas as entradas, mesmo que não seja possível encontrar um arranjo perfeito).

Nesse processo, primeiro tentaríamos acomodar cada restaurante de acordo com os requisitos absolutos - você pode pular essa parte do processo, pois ele só funciona quando os requisitos absolutos são relativamente pequenos em número; caso contrário, você acaba com um problema incrivelmente grande !

Na próxima etapa, criamos uma série de tabelas e atribuímos participantes aleatoriamente às tabelas para uma configuração inicial, e uma pontuação é calculada para representar o número de requisitos difusos que foram atendidos. Pares de clientes são alternados aleatoriamente e a pontuação é recalculada para essas tabelas para determinar se a nova configuração é preferível.

Idealmente, essa parte do processo deve ser repetida com várias configurações iniciais e pode ser facilmente calculada em paralelo.

Eu acho que qualquer organização de assentos válida é equivalente a um hipergrafo regular em | S | vértices, onde d é o número de jantares, com classificação no máximo ke máximo de codegree 1. A solução trivial é deixar todo mundo sempre sentado sozinho, mas acho que o objetivo é minimizar o número de mesas?