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 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