Skip to content

Instantly share code, notes, and snippets.

@joriki
Last active March 29, 2024 20:55
Show Gist options
  • Save joriki/4d2569d89b1bc92de14df4aea9ddc0b0 to your computer and use it in GitHub Desktop.
Save joriki/4d2569d89b1bc92de14df4aea9ddc0b0 to your computer and use it in GitHub Desktop.
Place party guests at dinner tables so they all meet each other; see https://math.stackexchange.com/questions/4622699.
import java.util.Random;
public class Question4622699 {
final static int nrounds = 7;
final static int ntables = 5;
final static int nchairs = 4;
final static int npeople = ntables * nchairs;
final static Random random = new Random();
static int [] [] counts = new int [npeople] [npeople];
static int [] [] [] groups = new int [nrounds] [ntables] [nchairs];
static int nrg;
static int count;
public static void main(String [] args) {
for (int i = 0;i < nrounds;i++) {
int [] left = new int [npeople];
for (int j = 0;j < npeople;j++)
left [j] = j;
for (int j = 0,l = npeople;j < ntables;j++)
for (int k = 0;k < nchairs;k++) {
int r = random.nextInt(l);
groups [i] [j] [k] = left [r];
left [r] = left [--l];
}
}
computeEnergy ();
int max = 0;
int n = 0;
for (double beta = 0;count < (npeople * (npeople - 1)) / 2;beta += 0.0000001) {
int round = random.nextInt(nrounds);
int [] [] g = groups [round];
int t1 = random.nextInt(ntables);
int t2 = random.nextInt(ntables - 1);
int c1 = random.nextInt(nchairs);
int c2 = random.nextInt(nchairs);
if (t2 >= t1)
t2++;
int oldNRG = nrg;
for (int i = 0;i < nchairs;i++) {
if (i != c1) {
decrement (g [t1] [c1],g [t1] [i]);
increment (g [t2] [c2],g [t1] [i]);
}
if (i != c2) {
decrement (g [t2] [c2],g [t2] [i]);
increment (g [t1] [c1],g [t2] [i]);
}
}
int t = g [t1] [c1];
g [t1] [c1] = g [t2] [c2];
g [t2] [c2] = t;
if (nrg > oldNRG && random.nextDouble () > Math.exp (beta * (oldNRG - nrg))) {
g [t2] [c2] = g [t1] [c1];
g [t1] [c1] = t;
for (int i = 0;i < nchairs;i++) {
if (i != c1) {
increment (g [t1] [c1],g [t1] [i]);
decrement (g [t2] [c2],g [t1] [i]);
}
if (i != c2) {
increment (g [t2] [c2],g [t2] [i]);
decrement (g [t1] [c1],g [t2] [i]);
}
}
}
max = Math.max(max,count);
if (++n % 0xfffff == 0)
System.out.println(beta + " : " + nrg + " / " + count + " / " + max);
}
print();
}
static void computeEnergy() {
for (int i = 0;i < nrounds;i++)
for (int j = 0;j < ntables;j++)
for (int k = 1;k < nchairs;k++)
for (int l = 0;l < k;l++)
if (l != k)
increment (groups [i] [j] [k],groups [i] [j] [l]);
}
static void increment (int i,int j) {
if (i < j) {
int t = i;
i = j;
j = t;
}
nrg += 2 * counts [i] [j] + 1;
if (counts [i] [j]++ == 0)
count++;
}
static void decrement (int i,int j) {
if (i < j) {
int t = i;
i = j;
j = t;
}
nrg -= 2 * counts [i] [j] - 1;
if (--counts [i] [j] == 0)
count--;
}
static void print () {
for (int i = 0;i < nrounds;i++) {
for (int j = 0;j < ntables;j++) {
for (int k = 0;k < nchairs;k++) {
System.out.format("%2d",groups [i] [j] [k]);
System.out.print(" ");
}
System.out.print(" ");
}
System.out.println();
}
}
}
@ntrel
Copy link

ntrel commented Mar 13, 2024

Thanks for this code. It was failing when I changed npeople to 13:

Exception in thread "main" java.lang.IllegalArgumentException: bound must be positive
	at java.base/java.util.Random.nextInt(Random.java:388)
	at Question4622699.main(Question4622699.java:24)

Then I realized that with 4 tables and 4 chairs I might as well set npeople to 16. That works and I can ignore 13, 14, 15 in the results unless extra guests come.

Unfortunately that means nrounds has to be 5 for 16 people, whereas for 13 theoretically it could do 4 rounds (meet 12 people, 3 per round). I tried a simple fix to avoid the exception but that made 0s on multiple tables per round - I think it's using 0 to show an empty chair, but 0 already means the first person, so it's not clear where the first person sits! Ideally it would use another symbol for unused chair.

@ntrel
Copy link

ntrel commented Mar 14, 2024

for 13 theoretically it could do 4 rounds (meet 12 people, 3 per round).

Sorry, later I realized because of the 3 empty chairs, on average only 2.76 people (36/13) can be met per person each round. So 5 rounds are needed.

@joriki
Copy link
Author

joriki commented Mar 15, 2024

@ntrel Thanks for the feedback. I don’t know why I made npeople a separate parameter; the code only works if it’s the product of ntables and nchairs. I’ve now set it accordingly.

@ntrel
Copy link

ntrel commented Mar 16, 2024

Great, thanks! We used your code for an event yesterday, and it worked very well.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment