Algoritmo combinatorio per l'assegnazione di persone ai gruppi

Question

Un collega è venuto da me con un problema interessante, uno pratico che ha a che fare con un gruppo di "nuove persone in città" di cui fa parte.

18 amici vogliono cenare in gruppo per ciascuno dei prossimi 4 giorni. Le regole sono le seguenti:

1. Ogni giorno il gruppo si dividerà in 4 gruppi di 4, e un gruppo di 2.
2. qualsiasi coppia di persone sarà solo vedere l'altro più di una volta nel corso della i 4 giorni.
3. Una determinata persona farà parte una volta al massimo del gruppo di dimensioni 2.

Una ricerca ricorsiva di forza bruta per un insieme valido di assegnazione di gruppo è ovviamente poco pratica. Ho gettato in una logica semplice per potare parti dell'albero il prima possibile, ma non abbastanza per renderlo pratico.

In realtà, sto iniziando a sospettare che potrebbe essere impossibile seguire tutte le regole, ma non riesco a trovare un argomento combinatorio per il motivo.

Qualche idea?

Answer 1

16 amici possono essere programmati 4x4 per 4 notti utilizzando due mutually orthogonal latin squares di ordine 4. Assegnare ciascun amico a una posizione distinta nella griglia 4x4. La prima notte, gruppo per fila. Al secondo, gruppo per colonna. Sulla terza, raggruppa per voce simile in latin square # 1 (rank della carta nell'esempio 4x4). Sulla quarta, raggruppa per voce simile nella casella n. 2 latina (seme della carta nell'esempio 4x4). In realtà, la costruzione del piano affine dà origine a tre quadrati latini tra loro ortogonali, quindi è possibile programmare una quinta notte, assicurando che ogni coppia di amici si incontri esattamente una volta.

Forse il programma per 16 potrebbe essere esteso, utilizzando la libertà della quinta notte inutilizzata.

MODIFICA: ecco il programma per 16 persone per 5 notti. Ogni riga è una notte. Ogni colonna è una persona. La voce è il gruppo a cui sono assegnati.

[0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3] 
[0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3] 
[0, 1, 2, 3, 1, 0, 3, 2, 2, 3, 0, 1, 3, 2, 1, 0] 
[0, 2, 3, 1, 1, 3, 2, 0, 2, 0, 1, 3, 3, 1, 0, 2] 
[0, 3, 1, 2, 1, 2, 0, 3, 2, 1, 3, 0, 3, 0, 2, 1]