Counting Dynkin systems

MO405736.py

def extend_closure(omega, included, extension, excluded):
	# We start with a closure which we want to extend
	closure = set(included)

	# Use a queue
	q = set([extension])
	while q:
		x = next(iter(q))
		q.remove(x)
		closure.add(x)

		# Ensure the complement closure too
		if (omega ^ x) not in closure:
			# Shortcut contradictions
			if (omega ^ x) in excluded:
				return None

			q.add(omega ^ x)

		for y in closure:
			if (x & y) == 0 and (x | y) not in closure:
				# Shortcut contradictions
				if (x | y) in excluded:
					return None

				q.add(x | y)

	return closure


def enumerate_dynkin(n):
	omega = (1 << n) - 1

	def inner(included, lb, excluded):
		yield sorted(included)

		for min in range(lb, (omega + 1) >> 1):
			if min in included or min in excluded:
				continue

			# Consider the implications of adding min
			ninc = extend_closure(omega, included, min, excluded)
			if ninc:
				for sys in inner(ninc, min + 1, set(excluded)):
					yield sys

			# Consider systems without min
			excluded.add(min)
			excluded.add(omega ^ min)

	for sys in inner(set([0, omega]), 1, set()): yield sys


for n in range(10):
	print(n, sum(1 for _ in enumerate_dynkin(n)))