Arranging people for table talks (block-design-ish?)

157 Views Asked by At

Say you have $N$ people and $T$ tables. Each person will visit every table over the course of $T$ sessions. We want to keep the distribution of people across the tables during the sessions as even as possible. As a secondary goal, we also want to mix people up as much as possible so that the same groups of people aren't going from table to table together.

I've seen several questions on SE about setting up similar networking events that had strict restrictions, such as the same number of people have to be at every table every session and no two people can be at the same table together more than once. This is a less restrictive version of this kind of problem, and I'd like to see if there are any clever ideas for how to go about setting this up.

In my particular problem, I have $N=50$ people and $T=6$ tables. So essentially I'm looking for 50 permutations of $[6]$ such that each position in the permutation contains each value roughly the same number of times, and the Hamming distance between any two permutations shouldn't be "too" small.

Since $6$ does not divide $50$, the best we can do for distribution is four tables of $8$ and two of $9$ for each session. How I've attacked the problem so far is to generate 50 random permutations of $[6]$ and then make swaps within various permutations in order to get the distributions correct for each session. This method optimized the distributions, but the Hamming distance suffered. I ended up with two permutations that were the same, and many others matched in three or four positions.

I'm wondering if there is a method to optimize both, or at least a procedure that can be followed to generate a set of arrangements that are good. This feels like a block-design problem, but I don't know enough about the different flavors of block-designs to know if this fits nicely into an already-solved category. Thank you.

1

There are 1 best solutions below

2
On BEST ANSWER

In some cases it may be easier to do a manual approach and get a quite good result

So for your $N=50$ people and $T=6$ tables, I produced a pattern which simply would not have complete duplicates and which I hoped would not have too many large partial duplicates

It did not quite have the four tables of $8$ and two of $9$ pattern but a couple of exchanges solved that. It then had $10/1225$ cases of matches in four positions but some arbitrary swaps (I probably tried about twenty) eliminated those, to produce the permutations in the table below

Of the $1225$ comparisons of the fifty permutations, this has $69$ cases of matches in three positions, $217$ cases of matches in two positions, $463$ cases of matches in one position, and $476$ cases of no matches in any position. Some matches in two positions are clearly inevitable, and I would not be surprised if some in three positions might be though probably fewer than $69$ as I made no effort to minimise these

1   2   3   4   5   6
1   2   4   3   6   5
1   2   5   3   4   6
1   3   4   5   6   2
1   4   5   6   2   3
1   4   6   3   5   2
1   5   2   4   6   3
1   5   6   2   3   4
1   6   2   3   4   5
2   1   3   6   4   5
2   1   4   3   5   6
2   3   1   4   5   6
2   3   6   5   1   4
2   4   1   6   5   3
2   4   3   1   6   5
2   5   3   1   4   6
2   6   3   4   1   5
2   6   4   5   3   1
3   1   5   6   2   4
3   1   6   2   4   5
3   2   5   1   6   4
3   4   5   2   6   1
3   5   1   6   4   2
3   5   6   1   2   4
3   6   4   5   1   2
3   6   5   4   2   1
4   1   2   5   3   6
4   2   1   3   5   6
4   3   2   5   6   1
4   3   5   6   1   2
4   3   6   2   5   1
4   5   1   6   2   3
4   5   2   6   3   1
4   6   2   1   5   3
5   1   3   2   6   4
5   1   4   2   3   6
5   2   1   4   6   3
5   2   4   6   3   1
5   3   6   4   1   2
5   4   6   1   3   2
5   6   3   1   4   2
5   6   4   1   2   3
6   1   5   2   3   4
6   2   1   5   4   3
6   3   1   4   2   5
6   3   2   1   4   5
6   4   2   3   1   5
6   4   3   5   2   1
6   5   3   2   1   4
6   5   4   3   1   2