# You have some evenly spaced collinear points, say, three or
# five. Your objective is to connect some of them with circles whose
# diameter is along the line, such that no two circles intersect
# except along the line.
# Here's a recursive way to generate all of the possibilities. For
# each point, we can either not connect it to anything, or we can
# connect it to any other point further along, as long as that
# wouldn't cross any other circles. In the base case, we return a
# single possibility: no circles. Also, we have two kinds of
# recursion: recursion that's not inside an immediately enclosing
# circle (so a circle all the way from n to max is valid) or recursion
# that is inside an immediately enclosing circle.
def inner_circles(n, max):
if n == max:
yield []
return
# don't connect point n to anything:
for possibility in circles(n+1, max):
yield possibility
# or do:
for linked_point in range(n+1, max):
for inner_possibility in inner_circles(n, linked_point):
for outer_possibility in circles(linked_point, max):
yield [(n, linked_point)] + inner_possibility + outer_possibility
def circles(n, max):
if n == max:
yield []
return
for possibility in inner_circles(n, max):
yield possibility
yield [(n, max)] + possibility
def nesting_problem(possibility):
for (start, end) in possibility:
for (start2, end2) in possibility:
if start > start2 and start < end2 and end > end2:
return (start, end), (start2, end2)
return None
# This verifies that a particular call of circles() returns no values
# with overlapping circles.
def check_circles(n, max):
for possibility in circles(n, max):
assert nesting_problem(possibility) is None, (nesting_problem(possibility), possibility)
# This provides us with a way to calculate the number of possibilities
# for a certain interval size.
n_inner_circles_cache = {}
def n_inner_circles(m):
try:
return n_inner_circles_cache[m]
except KeyError:
n_inner_circles_cache[m] = _n_inner_circles(m)
return n_inner_circles_cache[m]
def _n_inner_circles(m):
if m == 0:
return 1
n = n_circles(m-1)
for linked_point in range(1, m):
n += n_inner_circles(linked_point) * n_circles(m - linked_point)
return n
def n_circles(m):
if m == 0:
return 1
return 2 * n_inner_circles(m)
# nesting_problem also provides us with a brute-force way to verify (a
# particular call to) circles().
def brute_circles(n, max):
base_set = [(a, b) for a in range(n, max+1) for b in range(a+1, max+1)]
return (x for x in powerset(base_set) if not nesting_problem(x))
def powerset(some_set):
if not some_set:
yield []
return
for subset in powerset(some_set[1:]):
yield [some_set[0]] + subset
yield subset
# This verifies that at least up to n=7, the "efficient" algorithm
# given earlier does in fact produce the right results.
def check_brute(n):
for i in range(n):
bc = brute_circles(0, i)
c = circles(0, i)
assert (sorted(sorted(tuple(x)) for x in c) ==
sorted(sorted(tuple(x)) for x in bc)), (c, bc)
print "done with", i