Tournament decompositions in G9

MO441283_G9.py

#!/usr/bin/pypy3

from collections import defaultdict, Counter
from itertools import combinations, permutations

n = 4
directed_cycles = [(0,) + suffix for suffix in permutations(range(1, 2*n+1))]
print(len(directed_cycles), "vertices")

edge_idx = dict()
i = 0
for u, v in combinations(range(2*n+1), 2):
	edge_idx[(u, v)] = i
	edge_idx[(v, u)] = i
	i += 1

all_mask = (1 << i) - 1
edge_masks = [sum(1 << edge_idx[(u, v)] for u, v in zip(cyc, cyc[1:] + cyc[:1])) for cyc in directed_cycles]
dir_edge_masks = [sum(1 << edge_idx[(u, v)] for u, v in zip(cyc, cyc[1:] + cyc[:1]) if u < v) for cyc in directed_cycles]

vertexpair_masks = defaultdict(set)
memlimit_mask = (1 << 32) - 1 # Using the full 40320-bit mask as a key runs into problems
edges = 0
for i, j in combinations(range(len(edge_masks)), 2):
	if (edge_masks[i] & edge_masks[j]) == 0:
		vertexpair_masks[(edge_masks[i] | edge_masks[j]) & memlimit_mask].add((i,j))
		edges += 1
print(edges, "edges")


distrib = Counter()
progress = 0
for vpmask, ijs in vertexpair_masks.items():
	compmask = memlimit_mask ^ vpmask
	if compmask in vertexpair_masks:
		for kl in vertexpair_masks[compmask]:
			k, l = kl
			assert k < l
			for ij in ijs:
				i, j = ij
				assert i < j
				if j < k and (edge_masks[i] | edge_masks[j] | edge_masks[k] | edge_masks[l]) == all_mask:
					distrib[dir_edge_masks[i] | dir_edge_masks[j] | dir_edge_masks[k] | dir_edge_masks[l]] += 1
	progress += 1
	if progress % 1000 == 0:
		print("Progress", progress, "/", len(vertexpair_masks), ":", sum(distrib.values()), "quads so far")

print("Distrib:", Counter(distrib.values()))