S2T2

Jim Randell 9:11 am on 1 August 2023 Permalink Reply
Tags: by: Oliver D Anderson ( 2 )   

• 

  Jim Randell 9:11 am on 1 August 2023 Permalink | Reply

  This program constructs the different arrangement of bubbles. An empty bubble is represented by the empty tuple, and bubbles are enclosed by placing them in a tuple in order. But when the arrangement is printed we don’t print the outermost enclosing brackets of the tuple (which allows for separate bubbles).

  This Python program runs in 96ms. (Internal runtime is 37ms).

  Run: [ @replit ]

  from enigma import (decompose, cproduct, uniq, wrap, join, arg, printf)
  
  # generate unique configurations for <n> bubbles
  @wrap(uniq)
  def bubbles(n):
    if n == 0:
      yield ()
    else:
      # combine two smaller configurations
      for (x, y) in decompose(n, 2, increasing=1, sep=0, min_v=1):
        for (bx, by) in cproduct([bubbles(x), bubbles(y)]):
          yield tuple(sorted(bx + by))
      # or enclose n - 1 bubbles
      for b in bubbles(n - 1):
        yield (b,)
  
  # format a bubble configuration (default: without outermost enclosure)
  def fmt(bs, enc=""):
    return join((fmt(b, enc="()") for b in bs), sep=" ", enc=enc)
  
  n = arg(9, 0, int)
  printf("[bubbles({n})]")
  for (i, bs) in enumerate(bubbles(n), start=1):
    printf("{i}: {bs}", bs=fmt(bs))
  

  Solution: For 9 bubbles there are 719 configurations.

  The program is fast enough up to about 15 bubbles (235,381 configurations) without bothering about caching results.

  ---

  A configuration of bubbles can be represented as a tree, with an arc between bubble X and bubble Y if X directly contains Y. We also add arcs from a root bubble to all outermost bubbles (this does the job of the outermost enclosing tuple in my program above). And for n bubbles this gives us an unlabelled rooted tree with (n + 1) nodes.

  So we can count the number of bubble configurations by determining the number of unlabelled rooted trees.

  And this is sequence OEIS A000081, which has the following recurrence relation:

  

  Fortunately this is implemented fairly easily:

  Run: [ @replit ]

  from enigma import (irange, divisors, cache, arg, printf)
  
  # the number of different ways to draw diagrams with n bubbles is the
  # number of unlabelled rooted trees with (n + 1) nodes = OEIS A000081
  @cache
  def a(n):
    if n < 2: return n
    r = 0
    for k in irange(1, n - 1):
      r += sum(d * a(d) for d in divisors(k)) * a(n - k)
    return r // (n - 1)
  
  # number of configurations for <n> bubbles
  bubbles = lambda n: a(n + 1)
  
  n = arg(9, 0, int)
  k = bubbles(n)
  printf("{n} bubbles -> {k} arrangements")
  

  And this allows us to calculate much larger numbers (although for very large numbers we need to increase the recursion limit on the Python interpreter).

  LikeLike