Grupos de pessoas em diferentes mesas, sem repetir pessoas que já sentaram juntas

[andre_msantos]

Olá pessoal do fórum.

Estou tentando desenvolver uma planilha em Excel para auxiliar a organizar uma sessão de negócios, a ideia é a seguinte:
Possuo uma quantidade X de pessoas, preciso dividi-las em grupos de igual número e a um determinado intervalo de tempo essas pessoas tem que trocar de mesa, o intuito da sessão é que todos conversem com todos sem se repetir.
Quando possuo número de pessoas que tem como raiz um número primo eu consigo construir esses grupos baseados em uma matriz quadrada, mas esse fator me limita a dois grupos de 25 pessoas e de 49 pessoas. Gostaria de desenvolver uma planilha que eu colocasse o número de pessoas e a planilha me retornasse à quantidade de grupos ideais e também a mistura desses grupos. Comecei a pesquisar sobre combinação, porém preciso de algo que remova as interações repetidas, por exemplo, se eu tenho um grupo de 9 pessoas e vou dividi-las em grupos de três poderia ter ABC, ADE, AFG, ..., BCF, DEG o problema que nos dois últimos grupos as pessoas já tiveram interações entre si e isso não pode acontecer.
Alguém poderia me orientar sobre o que pesquisar? Obrigado

[jorgeluis]

André,
Acredito que o calculo pode ser feito por combinação dividindo o resultado pelo numero de pessoas.

1. Vejamos ABCDE (cada letra representando uma pessoa, total de 5 pessoas organizadas em grupos de 3):

C_5,3 = 5!/[3!(5-3)!]
C_5,3 = 10

10/5 = 2 (grupos possíveis: ABC - BDE)

2. Vejamos ABCDEF (cada letra representando uma pessoa, total de 6 pessoas organizadas em grupos de 3):

C_6,3 = 6!/[3!(6-3)!]
C_6,3 = 20

20/6 = 3 aproxim. (grupos possíveis: ABC - BDE - CDF)

3. Vejamos ABCDEFG (cada letra representando uma pessoa, total de 7 pessoas organizadas em grupos de 3):

C_7,3 = 7!/[3!(7-3)!]
C_7,3 = 35

35/7 = 5 (grupos possíveis: ABC - BDE - CDF - CEG - EFG)

.
.
.

[jorgeluis]

corrigindo...

André,
Acredito que o calculo pode ser feito por combinação, dividindo o resultado pelo numero de pessoas menos 1. Considerando apenas o valor inteiro, arredondado, do resultado.

1. Vejamos ABCDE (cada letra representando uma pessoa, total de 5 pessoas organizadas em grupos de 3):

C_5,3 = 5!/[3!(5-3)!]
C_5,3 = 10

10/(5-1) = 2 aproxim. (grupos possíveis: ABC - BDE)

2. Vejamos ABCDEF (cada letra representando uma pessoa, total de 6 pessoas organizadas em grupos de 3):

C_6,3 = 6!/[3!(6-3)!]
C_6,3 = 20

20/(6-1) = 4 (grupos possíveis: ABC - BDE - CDF -AEF)

3. Vejamos ABCDEFG (cada letra representando uma pessoa, total de 7 pessoas organizadas em grupos de 3):

C_7,3 = 7!/[3!(7-3)!]
C_7,3 = 35

35/(7-1) = 6 aproxim. (grupos possíveis: ABC - BDE - CDF - AEF - BFG -CEG)

.
.
.

[jorgeluis]

Esquece André, desculpe,
o raciocínio está incorreto, pois, conforme aumenta o número de pessoas o número de grupos aumenta desproporcionalmente.
perdão !!!
mas, vou continuar tentando achar uma forma de resolver isso.

[andre_msantos]

Olá Jorge,

Achei interessante a forma como você coloquei, vi que existem algumas restrições, já procurei em diversos lugares, inclusive em inglês mas só encontrei soluções com matriz quadrada de número primo, estou pensando em elaborar algum algoritmo que desenvolva todas as interações e selecione o conjunto deles que menos se repetem, pois em alguns casos, como com 16 pessoas você precisaria repetir algumas interações para que todos possam se encontrar com todos, o meu maior problema, pensando de acordo com seu raciocínio é como eu consigo chegar num número adequado de pessoas por grupo, acredito que esse seja meu maior problema. Caso vocês tenham interesse segue o link da solução através de matrizes http://ask.metafilter.com/161031/Dont-meet-the-same-person-twice-involves-math-somehow. Caso eu chegue em uma solução retorno aqui e compartilho. Muito obrigado pela ajuda até agora.

[vini.almendro]

Também possuo interesse sem resolver esse problema! Até o momento só encontrei a solução quando trabalhamos em uma matriz com número de linhas e colunas sendo um número primo, como 5x5,7x7,11x11 ...