Skip to content

Instantly share code, notes, and snippets.

@joriki
Created March 18, 2024 10:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save joriki/402615bc5a18cbe22543a62f6117a84a to your computer and use it in GitHub Desktop.
Save joriki/402615bc5a18cbe22543a62f6117a84a to your computer and use it in GitHub Desktop.
Count the schedules for round-robin tournaments; see https://math.stackexchange.com/questions/4882568
import java.util.BitSet;
public class Question4882568 {
static boolean [] [] played;
static int count;
static int n;
public static void main (String [] args) {
for (n = 2;;n += 2) {
count = 0;
played = new boolean [n] [n];
recurse (null,n,0);
System.out.println(n + " : " + count);
}
}
static void recurse (BitSet matched,int daysLeft,int unmatched) {
if (daysLeft == 0)
count++;
else if (unmatched == 0)
recurse (new BitSet (n),daysLeft - 1,n);
else {
int toMatch = matched.nextClearBit (0);
matched.set (toMatch);
int team = toMatch;
for (;;) {
team = matched.nextClearBit (team + 1);
if (team == n)
break;
if (!played [toMatch] [team]) {
set (toMatch,team,true);
matched.set (team);
recurse (matched,daysLeft,unmatched - 2);
matched.clear (team);
set (toMatch,team,false);
}
}
matched.clear (toMatch);
}
}
static void set (int i,int j,boolean value) {
played [i] [j] = played [j] [i] = value;
}
}
@ColmBhandal
Copy link

ColmBhandal commented Mar 21, 2024

From what I can see, this algorithm brute forces everyone combination. If so I believe it can be made more efficient by noting that WLOG you can select one team, say team zero, and fix all of its matches to any permutation of the remaining n-1 teams. By symmetry, the amount of combinations is the same no matter what permutation you choose. So the algorithm could fix the permutation e.g. at 1,2,....,n-1, schedule and count, and then multiply by (n-1)! afterwards.

I did a Gist to show this: https://gist.github.com/ColmBhandal/a33b15410a5c12f633b36eb81c67da26.

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