<p>Here's a (loose?) upper bound on the number of meals you can serve.</p>

<p>Let $|S| = n$ and assume that $n$ is divisible by $k$. Also, assume that you have exactly $n/k$ tables and you want each table to be full during each meal.</p>

<p>For each meal, construct a graph with a node for each person in $S$ and an edge when two people share a table. This graph is a collection of $n/k$ cliques each of size $k$. Thus the number of edges in the graph is $\Theta(nk)$.</p>

<p>Since you don't want any edge to occur in two different meals, and since the total number of edges possible on a vertex set of size $n$ is $\Theta(n^2)$, this shows you can only serve $O(n/k)$ meals.</p>

<p>Actually, it's not difficult to find the constants here and when you do the math, you get an upper bound of exactly $\frac{n-1}{k-1}$, which, for your typical values, is 11.</p>

CC BY-SA 3.0
2013-02-18T16:08:00.810Z
2013-02-18T16:40:50.757Z
2013-02-18T16:40:50.757Z
Vinayak Pathak
<p>If you want any two people to sit at the same table exactly once, then this is called a <a href="http://en.wikipedia.org/wiki/Block_design#Resolvable_2-designs" rel="nofollow">resolvable 2-design</a> and has been studied a lot. Of course allowing to skip a few meals would give a solution to your problem when two people can meet at most once. (But other solutions might exist, I suppose.)</p>

CC BY-SA 3.0
2013-02-18T14:01:18.627Z
I would like two people to meet at most once. The identity of the table is not an issue and I'm not sure about the significance of _to sit at the same table_ as part of your answer but will look up the linked definition.
Christian Lindig
CC BY-SA 3.0
2013-02-18T13:14:16.470Z
2013-02-18T13:14:16.470Z
domotorp
<p>I'm not sure if you require a deterministic algorithm, but I've solved a similar problem in the past using a <a href="http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo" rel="nofollow">Markov chain Monte Carlo method</a>.</p>

<p>You can see <a href="https://github.com/ChimeraCoder/FreeSeat" rel="nofollow">a working example of this approach on Github</a> - this program attempts to seat a group of people at tables of a fixed size, given a set of seating constraints which may be either positive or negative ("must" or "must not"), and either absolute or relative ("preferable").</p>

<p>Note: this program doesn't solve <em>exactly</em> the same problem that you propose, but it does give a working demonstration of a Markov chain Monte Carlo method, and it's close enough that you can easily adjust it as needed for your problem.</p>

<p>The program solves the problem for one dinner, but in your case, an easy way of approaching the problem would be to run the algorithm once for each dinner, each time providing each diner's previous companions as either fuzzy or absolute negative requirements. (The advantage of fuzzy requirements is that you are guaranteed that the algorithm will halt on all inputs, even if a perfect arrangement cannot be found).</p>

<p>In this process, we would first attempt to seat each diner according to the absolute requirements - you may want to skip this part of the process, since it only works when the absolute requirements are relatively small in number; otherwise you end up with <a href="http://en.wikipedia.org/wiki/Boolean_satisfiability_problem" rel="nofollow">an incredibly huge problem</a>!</p>

<p>In the next step, we create a series of tables and randomly assign participants to the tables for an initial configuration, and a score is calculated to represent the number of fuzzy requirements that have been satisfied. Pairs of diners are randomly switched, and the score is recalculated for those tables to determine whether the new configuration is preferable.</p>

<p>This part of the process should ideally be repeated with several initial configurations, and can easily be computed in parallel.</p>

CC BY-SA 3.0
2013-02-17T20:32:40.967Z
Interesting and +1 for showing us code. I thought about randomly drawing table configurations and trying to iterate on those where collisions happen. Simulated annealing came also to mind. For my particular case it would be even enough to pre-compute configurations for various $|S|$.
Christian Lindig
CC BY-SA 3.0
2013-02-17T15:56:59.527Z
2013-02-17T15:56:59.527Z
chimeracoder
<p>I think any valid seating arrangement is equivalent to a d-regular hypergraph on |S| vertices, where d is the number of dinners, with rank at most k and maximum codegree 1.  The trivial solution is to have everyone always sit by themselves, but I guess the goal is to minimize the number of tables?</p>

CC BY-SA 3.0
2013-02-18T03:04:48.270Z
The number of tables is fixed in this setting. And it's strictly less than the number of people.
Suresh Venkat
CC BY-SA 3.0
2013-02-17T23:17:40.553Z
2013-02-17T23:17:40.553Z
Travis
<p>Here's a variant of the original answer (below) that gives the desired setting: tables of size 5, 45 people, and 10 meals, except that one meal has a few tables of size 4.</p>

<p>Let $F$ be the field of size 9.  Pick 4 vertical, degenerate lines  $\{(b,x) | x \in F\}$ for every $b = 0,1,2,3$ and declare their people "empty."  We are left with 81 - 9x4 = 45 people.</p>

<p>9 meals are given by slopes $a = 0,1,\ldots,8$.  The intersections with the 4 empty degenerate lines reduce the table size to 9-4=5.</p>

<p>An additional meal is given by the remaining degenerate lines $\{(b,x) | x \in F\}$ for every $b = 4,5,6,7,8$.  Here the table size is 9.  However (in any solution) we can break a table of size 9 into a table of size 5 and one of size 4.</p>

<p>If there are a few more people one can use the field of size 11.</p>

<hr>

<p>First let us handle $k^2$ people and $k$ meals.</p>

<p>Pick a finite field $F$ of size $k$ and identify people with $F \times F$.  To each meal there corresponds a slope, to a table a line parallel to that slope.</p>

<p>Specifically, meal $a$ has $k$ tables $\{(x,ax+b) | x \in F\}$ for every $b \in F$.</p>

<p>The intersection property you want is the fact that lines with distinct slopes intersect in exactly one point.</p>

<hr>

<p>To handle $2k^2$ people, divide them up in two groups of $k^2$ each, and apply the construction above to each group.  To handle $2k^2 - k = 45$, label (in the first group) a fixed line such as $\{(x,x)|x\in F\}$ as "empty."  You may have a few tables with $k-1$ people.</p>

<p>For more meals one could e.g. pick a different partition in two groups at the beginning of the 6th meal. (Say you interleave the original partition, to ensure that the two groups "mix.") Though of course this may result in some intersections.</p>

CC BY-SA 3.0
2013-02-17T20:29:03.620Z
This is an interesting construction but too limiting for my particular case because of $|S|=k^2$ but could server as a lower limit.
Christian Lindig
CC BY-SA 3.0
2013-02-17T21:46:24.460Z
I have edited the question to address more general parameters.
Manu
CC BY-SA 3.0
2013-02-19T09:06:50.517Z
I believe that [block design] (http://en.wikipedia.org/wiki/Block_design) is the appropriate framework for the general case, as pointed out by [domotorp](http://cstheory.stackexchange.com/users/419/domotorp) below. However, I like the constructive aspect of this and accept is as a good answer.
Christian Lindig
CC BY-SA 3.0
2013-02-19T14:43:38.983Z
I am curious if a solution with 10 meals exists; I did some googling but couldn't find an answer. Anyway, once the best solution has been found, what about coding it up so that organizers can paste partecipants' names and get back all seats assignments?  Would that be useful to them?  If we make this simpler other workshops may adopt this nice tradition of Dagstuhl.
Manu
CC BY-SA 3.0
2013-02-22T04:25:51.697Z
Nice update. We should drink a beer at Dagstuhl in your honor if this gets implemented :)
Suresh Venkat
CC BY-SA 3.0
2013-02-22T08:09:52.797Z
Anyone coming to Dagstuhl please stop by my office to discuss this. There are many more aspects to this and I don't have time to implement this right away but I'm quite interested.
Christian Lindig
CC BY-SA 3.0
2013-02-22T13:29:49.787Z
I am not coming to Dagstuhl in the near future.  Could you elaborate on the additional aspects?  Coding this up on the web is easy, but there are probably other "implementation" issues.
Manu
CC BY-SA 3.0
2013-02-22T15:08:12.173Z
I've sent you an email. If more people are interested I'm happy to discuss this by email collectively.
Christian Lindig
CC BY-SA 3.0
2013-02-17T14:59:06.753Z
2013-02-22T13:22:52.620Z
2013-02-22T13:22:52.620Z
Manu
<p>Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that nobody shares a table with the same person twice. Typical values are $|S|=45$ and $k=5$ and 6 to 10 meals.</p>

<p>Put in a more abstract way, I'd like to find a sequence of partitions of $S$ such that each partition consists of pairwise disjoint subsets of cardinality $k$ and the added global property that any intersection between two such subsets contains no more than one element. I suspect this can be formulated as a graph theoretical or combinatorical problem. </p>

<p>I'd be grateful for a better formulation of the problem and pointers to relevant literature as it is outside of my domain.</p>

<p>The background: this could be used for seating arrangements at <a href="http://www.dagstuhl.de">Schloss Dagstuhl</a> where many computer scientists come to discuss their research over the course of a week. Currently seating is done randomly and unsurprisingly some people find themselves sitting with the same people twice (or more often) over the course of a week. Also unsurprisingly, we receive some complaints about this and vague suggestions how to improve this. I'd like to understand this better. A stronger formulation of the problem involves optimizing who is sitting next to each other but I believe this is not relevant for tables of size 5. </p>

<p>Outside of the application I think the interesting question is for the maximum number of meals that can be served for a given $S$ and $k$, i.e., how many such partitions exist.</p>

CC BY-SA 3.0
2013-02-16T19:53:09.560Z
IIRC, this sounds like the Hamilton-Waterloo problem.
Juho
CC BY-SA 3.0
2013-02-16T21:34:58.143Z
From glancing at a paper about the Hamilton-Waterloo problem I get the impression that it deals with the stricter problem of ensuring that a participant sits next to each other participant exactly once.
Christian Lindig
CC BY-SA 3.0
2013-02-18T15:58:27.770Z
[Kirkman's schoolgirl problem](http://en.wikipedia.org/wiki/15_schoolgirl_problem) seems to be of similar nature and might be a starting point.
Christian Lindig
<graph-theory><co.combinatorics>
Good seating arrangements for sequence of meals and tables of size k for a group of people
Christian Lindig
# Good seating arrangements for sequence of meals and tables of size k for a group of people

(Asked by: username_0 on 2013-02-16)

Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that nobody shares a table with the same person twice. Typical values are $|S|=45$ and $k=5$ and 6 to 10 meals.

Put in a more abstract way, I'd like to find a sequence of partitions of $S$ such that each partition consists of pairwise disjoint subsets of cardinality $k$ and the added global property that any intersection between two such subsets contains no more than one element. I suspect this can be formulated as a graph theoretical or combinatorical problem.

I'd be grateful for a better formulation of the problem and pointers to relevant literature as it is outside of my domain.

The background: this could be used for seating arrangements at [Schloss Dagstuhl](http://www.dagstuhl.de) where many computer scientists come to discuss their research over the course of a week. Currently seating is done randomly and unsurprisingly some people find themselves sitting with the same people twice (or more often) over the course of a week. Also unsurprisingly, we receive some complaints about this and vague suggestions how to improve this. I'd like to understand this better. A stronger formulation of the problem involves optimizing who is sitting next to each other but I believe this is not relevant for tables of size 5.

Outside of the application I think the interesting question is for the maximum number of meals that can be served for a given $S$ and $k$, i.e., how many such partitions exist.

**Tags:** graph-theory, co.combinatorics

> **Comments:**
> **username_1**: IIRC, this sounds like the Hamilton-Waterloo problem.  
> **username_0**: From glancing at a paper about the Hamilton-Waterloo problem I get the impression that it deals with the stricter problem of ensuring that a participant sits next to each other participant exactly once.  
> **username_0**: [Kirkman's schoolgirl problem](http://en.wikipedia.org/wiki/15_schoolgirl_problem) seems to be of similar nature and might be a starting point.  

---

## 5 answers

### Answer by username_7 on 2013-02-17. Score: 11 | Accepted answer

Here's a variant of the original answer (below) that gives the desired setting: tables of size 5, 45 people, and 10 meals, except that one meal has a few tables of size 4.

Let $F$ be the field of size 9. Pick 4 vertical, degenerate lines $\{(b,x) | x \in F\}$ for every $b = 0,1,2,3$ and declare their people "empty." We are left with 81 - 9x4 = 45 people.

9 meals are given by slopes $a = 0,1,\ldots,8$. The intersections with the 4 empty degenerate lines reduce the table size to 9-4=5.

An additional meal is given by the remaining degenerate lines $\{(b,x) | x \in F\}$ for every $b = 4,5,6,7,8$. Here the table size is 9. However (in any solution) we can break a table of size 9 into a table of size 5 and one of size 4.

If there are a few more people one can use the field of size 11.

---

First let us handle $k^2$ people and $k$ meals.

Pick a finite field $F$ of size $k$ and identify people with $F \times F$. To each meal there corresponds a slope, to a table a line parallel to that slope.

Specifically, meal $a$ has $k$ tables $\{(x,ax+b) | x \in F\}$ for every $b \in F$.

The intersection property you want is the fact that lines with distinct slopes intersect in exactly one point.

---

To handle $2k^2$ people, divide them up in two groups of $k^2$ each, and apply the construction above to each group. To handle $2k^2 - k = 45$, label (in the first group) a fixed line such as $\{(x,x)|x\in F\}$ as "empty." You may have a few tables with $k-1$ people.

For more meals one could e.g. pick a different partition in two groups at the beginning of the 6th meal. (Say you interleave the original partition, to ensure that the two groups "mix.") Though of course this may result in some intersections.

> **Comments:**
> **username_0**: This is an interesting construction but too limiting for my particular case because of $|S|=k^2$ but could server as a lower limit.  
> **username_7**: I have edited the question to address more general parameters.  
> **username_0**: I believe that [block design] (http://en.wikipedia.org/wiki/Block_design) is the appropriate framework for the general case, as pointed out by [username_3](http://cstheory.stackexchange.com/users/419/username_3) below. However, I like the constructive aspect of this and accept is as a good answer.  
> **username_7**: I am curious if a solution with 10 meals exists; I did some googling but couldn't find an answer. Anyway, once the best solution has been found, what about coding it up so that organizers can paste partecipants' names and get back all seats assignments?  Would that be useful to them?  If we make this simpler other workshops may adopt this nice tradition of Dagstuhl.  
> **username_6**: Nice update. We should drink a beer at Dagstuhl in your honor if this gets implemented :)  
> **username_0**: Anyone coming to Dagstuhl please stop by my office to discuss this. There are many more aspects to this and I don't have time to implement this right away but I'm quite interested.  
> **username_7**: I am not coming to Dagstuhl in the near future.  Could you elaborate on the additional aspects?  Coding this up on the web is easy, but there are probably other "implementation" issues.  
> **username_0**: I've sent you an email. If more people are interested I'm happy to discuss this by email collectively.  

---

### Answer by username_2 on 2013-02-18. Score: 4

Here's a (loose?) upper bound on the number of meals you can serve.

Let $|S| = n$ and assume that $n$ is divisible by $k$. Also, assume that you have exactly $n/k$ tables and you want each table to be full during each meal.

For each meal, construct a graph with a node for each person in $S$ and an edge when two people share a table. This graph is a collection of $n/k$ cliques each of size $k$. Thus the number of edges in the graph is $\Theta(nk)$.

Since you don't want any edge to occur in two different meals, and since the total number of edges possible on a vertex set of size $n$ is $\Theta(n^2)$, this shows you can only serve $O(n/k)$ meals.

Actually, it's not difficult to find the constants here and when you do the math, you get an upper bound of exactly $\frac{n-1}{k-1}$, which, for your typical values, is 11.


---

### Answer by username_3 on 2013-02-18. Score: 3

If you want any two people to sit at the same table exactly once, then this is called a [resolvable 2-design](http://en.wikipedia.org/wiki/Block_design#Resolvable_2-designs) and has been studied a lot. Of course allowing to skip a few meals would give a solution to your problem when two people can meet at most once. (But other solutions might exist, I suppose.)

> **Comments:**
> **username_0**: I would like two people to meet at most once. The identity of the table is not an issue and I'm not sure about the significance of _to sit at the same table_ as part of your answer but will look up the linked definition.  

---

### Answer by username_4 on 2013-02-17. Score: 2

I'm not sure if you require a deterministic algorithm, but I've solved a similar problem in the past using a [Markov chain Monte Carlo method](http://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo).

You can see [a working example of this approach on Github](https://github.com/ChimeraCoder/FreeSeat) - this program attempts to seat a group of people at tables of a fixed size, given a set of seating constraints which may be either positive or negative ("must" or "must not"), and either absolute or relative ("preferable").

Note: this program doesn't solve *exactly* the same problem that you propose, but it does give a working demonstration of a Markov chain Monte Carlo method, and it's close enough that you can easily adjust it as needed for your problem.

The program solves the problem for one dinner, but in your case, an easy way of approaching the problem would be to run the algorithm once for each dinner, each time providing each diner's previous companions as either fuzzy or absolute negative requirements. (The advantage of fuzzy requirements is that you are guaranteed that the algorithm will halt on all inputs, even if a perfect arrangement cannot be found).

In this process, we would first attempt to seat each diner according to the absolute requirements - you may want to skip this part of the process, since it only works when the absolute requirements are relatively small in number; otherwise you end up with [an incredibly huge problem](http://en.wikipedia.org/wiki/Boolean_satisfiability_problem)!

In the next step, we create a series of tables and randomly assign participants to the tables for an initial configuration, and a score is calculated to represent the number of fuzzy requirements that have been satisfied. Pairs of diners are randomly switched, and the score is recalculated for those tables to determine whether the new configuration is preferable.

This part of the process should ideally be repeated with several initial configurations, and can easily be computed in parallel.

> **Comments:**
> **username_0**: Interesting and +1 for showing us code. I thought about randomly drawing table configurations and trying to iterate on those where collisions happen. Simulated annealing came also to mind. For my particular case it would be even enough to pre-compute configurations for various $|S|$.  

---

### Answer by username_5 on 2013-02-17. Score: 0

I think any valid seating arrangement is equivalent to a d-regular hypergraph on |S| vertices, where d is the number of dinners, with rank at most k and maximum codegree 1. The trivial solution is to have everyone always sit by themselves, but I guess the goal is to minimize the number of tables?

> **Comments:**
> **username_6**: The number of tables is fixed in this setting. And it's strictly less than the number of people.  

---

