I implemented the integral maximum flow construction that's used to prove Baranyai's theorem. More details in your favorite textbook covering factors of a complete hypergraph.
from collections import defaultdict
from fractions import Fraction
from math import factorial
from operator import itemgetter
def binomial(n, k):
return factorial(n) // (factorial(k) * factorial(n - k))
def find_path(graph, s, t):
stack = [s]
predecessor = {s: t}
while stack:
v = stack.pop()
for u in graph[v]:
if u not in predecessor:
stack.append(u)
predecessor[u] = v
assert t in predecessor
path = [t]
while path[-1] != s:
path.append(predecessor[path[-1]])
path.reverse()
return path
def round_flow(flow):
while True:
capacities = []
for (u, v), x in flow.items():
z = x - x.numerator // x.denominator
if z:
capacities.append(((v, u), z))
capacities.append(((u, v), 1 - z))
if not capacities:
break
(t, s), delta = min(capacities, key=itemgetter(1))
graph = defaultdict(list)
for (v, u), z in capacities:
if (v, u) not in [(s, t), (t, s)]:
graph[v].append(u)
path = find_path(graph, s, t)
for i, v in enumerate(path):
u = path[i - 1]
if (u, v) in flow:
flow[(u, v)] += delta
else:
flow[(v, u)] -= delta
def baranyai(n, k):
m, r = divmod(n, k)
assert not r
M = binomial(n - 1, k - 1)
partition = [[()] * m for i in range(M)]
for l in range(n):
flow = defaultdict(Fraction)
for i, A_i in enumerate(partition):
for S in A_i:
flow[(i, S)] += Fraction(k - len(S), n - l)
round_flow(flow)
next_partition = []
for i, A_i in enumerate(partition):
next_A_i = []
for S in A_i:
if flow[(i, S)]:
next_A_i.append(S + (l,))
flow[(i, S)] -= 1
else:
next_A_i.append(S)
next_partition.append(next_A_i)
partition = next_partition
assert len(partition) == M
classes = set()
for A in partition:
assert len(A) == m
assert all(len(S) == k for S in A)
assert len({x for S in A for x in S}) == n
classes.update(map(frozenset, A))
assert len(classes) == binomial(n, k)
return partition
if __name__ == '__main__':
print(baranyai(9, 3))
print(baranyai(20, 2))
Let me dump an email that I wrote about this answer here, since it may be useful to others.
Unfortunately there's nothing that would be better suited as a source for transliteration.
The construction I used is due to Brouwer and Schrijver (1979). I could see only half of it at the time because I was looking on Google Books, but there's a PDF floating around now. It's a high-level mathematical description of an inductive proof that sets up a max flow problem, exhibits a fractional solution, and asserts the existence of an integer solution without going into detail about how to get it. My Python implementation used pipage rounding to follow the exact structure of the proof, but if you're just trying to get work done I would suggest calling out to an R library that computes max flows (e.g., igraph).
Let me dash off a concrete example of how to set up the max flows because the abstract proof was pretty mysterious to me before I figured it out. The smallest non trivial example is n=6 and k=3. This means we have (6-1) choose (3-1) = 10 partitions, each with 2 sets of size 3. Starting off with a 10 by 2 by 3 array having all elements blank, the B&S proof calls for us to place the 1s (one per row), then the 2s, then ..., then the 6s. Placing the 1s is boring due to symmetry considerations, so I'll just do it without explanation. (You don't need to special case this in code.)
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
Starting with the 2s, things get interesting. The key invariant in intuitive English is that we want each censored subset to appear exactly as many times as we would expect. Of the 6 choose 3 = 20 size-3 subsets of {1, 2, ..., 6} with numbers >2 censored with , there are 4 choose 1 = 4 subsets that look like {1,2,} and 4 choose 2 = 6 that look like {1,,} and 4 choose 2 = 6 that look like {2,,} and 4 choose 3 = 4 that look like {,,_}. What we want to do is place one 2 in each row to get this distribution. Easy enough to do this one by hand:
{1,2,_}, {_,_,_}
{1,2,_}, {_,_,_}
{1,2,_}, {_,_,_}
{1,2,_}, {_,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}
When we get to 3 we have 3 choose 0 = 1x {1,2,3}, 3 choose 1 = 3x {1,2,}, 3x {1,3,}, 3x {2,3,}, 3 choose 2 = 3x {1,,}, 3x {2,,}, 3x {3,,}, 3 choose 3 = 1x {,,}. Actual choices to make! This is where max flow comes in.
Let ell be the number that we're placing. The flow network we construct has a source, a vertex for each row, a vertex for each censored subset containing ell, and a sink. There is an arc from the source to each row vertex of capacity 1. There is an arc from each censored subset S to the sink of capacity (n-1 - ell) choose (k - |S|). There is an arc of capacity 1 from each row vertex to each censored subset that could appear in that row if we placed ell there.
Lettering the rows a..j, the middle arcs look like
a-->{1,2,3}
a-->{3,_,_}
b-->{1,2,3}
b-->{3,_,_}
c-->{1,2,3}
c-->{3,_,_}
d-->{1,2,3}
d-->{3,_,_}
e-->{1,3,_}
e-->{2,3,_}
...
j-->{1,3,_}
j-->{2,3,_}
Get an integral max flow, which will place exactly one ell in each row. The placement looks something like
{1,2,3}, {_,_,_}
{1,2,_}, {3,_,_}
{1,2,_}, {3,_,_}
{1,2,_}, {3,_,_}
{1,3,_}, {2,_,_}
{1,3,_}, {2,_,_}
{1,3,_}, {2,_,_}
{1,_,_}, {2,3,_}
{1,_,_}, {2,3,_}
{1,_,_}, {2,3,_}
And on it goes until we get
{1,2,3}, {4,5,6}
{1,2,4}, {3,5,6}
{1,2,5}, {3,4,6}
{1,2,6}, {3,4,5}
{1,3,4}, {2,5,6}
{1,3,5}, {2,4,6}
{1,3,6}, {2,4,5}
{1,4,5}, {2,3,6}
{1,4,6}, {2,3,5}
{1,5,6}, {2,3,4}
Hope this helps!
