Created
March 18, 2024 10:57
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.