Compute the Bang Bang numbers

bangbang_counter.py

#!/usr/bin/python
# -*- encoding: utf-8 -*-

# See http://shadabahmed.com/blog/2013/08/16/bang-bang for context.

# A string of single and double quotes may be interpreted as an element
# of the symmetric group S3, since there are three quotation states when
# lexing a shell command: unquoted, single-quoted, and double-quoted,
# and each string permutes the quotation state. A single quote mark
# switches between unquoted and single-quoted, and a double quote mark
# switches between unquoted and double-quoted. These transpositions form
# a basis for S3. So for our purposes there are six distinct quotation
# states to keep track of.

# We’ll represent an element of S3 as a three-tuple, consisting of the
# numbers 0,1,2 in some order.

# A string containing instances of !! is represented by a mapping from
# S3 to the natural numbers, indicating how many occurences of !! there
# are in each quotation state.

# You can think of these mappings as elements of the group semiring N[S3],
# if you want to be algebraic about it: this viewpoint leads to a recurrence
# relation for these numbers, which is an even more efficient way to
# compute them. See http://wp.me/pZjY-hS for details.

# These are the initial strings
a = {(1,0,2): 1}                # : '!!'
b = {(2,1,0): 1, (1,0,2): 1}    # : "!!" '!!'

def total(a):
    """The total number of occurences of !! in a.
    """
    return sum(a.values())

def compose(a, b):
    """Compose two elements of S3: a then b.
    """
    return (b[a[0]], b[a[1]], b[a[2]])

def substitute(x, y):
    """Replace all non-single-quoted instances of !! in x by y.
    """
    result = {}
    for p, n in x.iteritems():
        if p[0] == 1:
            # These are single-quoted, so they stay as they were
            result[p] = result.get(p, 0) + n
        else:
            # Add in the elements of y
            for q, m in y.iteritems():
                r = compose(p, q)
                result[r] = result.get(r, 0) + m*n
    return result

print "0:", total(a)
print "1:", total(b)
x = substitute(b, a)
for i in range(19):
    print "%d: %d" % (i+2, total(x))
    x = substitute(x, x)