1
$\begingroup$

I have $N$ guests and $M$ tables with $L$ seats each ($N\leq M\cdot L$). My task is it to distribute the guests for $N\geq D\geq3$ rounds such that no guest will sit on the same table, and he will never meet the same guests again.

As example: I have four guests, and two tables, with two seats each. Then I can distribute my guests as following:

In the first round: 
T1: [1, 2]  
T2: [3, 4]  
In the second round: 
T1: [3, 1] //Already a problem!
T2: [2, 4] //Already a problem!

I tried to find an algorithm, but until now I failed. My initial approaches were either using the distribution of the guests in a matrix, and then using the columns, rows, and diagonals for at least three rounds, but that approach failed in the third round already. The other approach was using a "labyrinth-solving" approach by using a recursive function. But is there a mathematical approach how to solve that problem?

$\endgroup$

1 Answer 1

0
$\begingroup$

My solution for $D=3$ was:
Initially, every guest is assigned a position in a matrix with the size $L\times M$ according to his guest number. For the second round, the matrix is transposed to a matrix with the size $M\times L$, and reshaped to $L\times M$ afterwards. For the final round, the diagonals are used for creating the final seating list.
As example (for four guests and four tables with four seats each, each row gives one table):
Round 1: $$\begin{pmatrix} 1 & 2 & 3 & 4\\ 5 & 6 & 7 & 8\\ 9 & 10 & 11 & 12\\ 13 & 14 & 15 & 16\end{pmatrix}$$ Round 2: $$\begin{pmatrix} 1 & 5 & 9 & 13\\ 2 & 6 & 10 & 14\\ 3 & 7 & 11 & 15\\ 4 & 8 & 12 & 16\end{pmatrix}$$ And for the final round: $$\begin{pmatrix} 1 & 6 & 11 & 16\\ 2 & 7 & 12 & 13\\ 3 & 8 & 9 & 14\\ 4 & 5 & 10 & 15\end{pmatrix}$$

Nevertheless it has to be mentioned that that does not fulfill the requirement of changing tables, only of changing the people you sit at the table with. Even though this requirement was stated in the original question, finally it was dropped in my application, thus my solution worked out for me.

$\endgroup$
2
  • $\begingroup$ Doesn't this have guest $1$ sitting in the exact same spot for the whole event? $\endgroup$
    – Christoph
    Jun 21, 2018 at 12:04
  • $\begingroup$ Hmm, yes, did not see that requirement, so that solution would be difficult. Nevertheless it was the solution I used in the end, thus I intended to provide it as a possible answer here for others to find. $\endgroup$
    – arc_lupus
    Jun 21, 2018 at 12:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .