BF Trees

bfmemo.py

import itertools
import time

COUNTS_SUMMING = {0: [[]]}
def counts_summing(n):
    if n not in COUNTS_SUMMING:
        sums = []
        for first in range(1, n+1):
            for rest in counts_summing(n - first):
                sums.append([first] + rest)
        COUNTS_SUMMING[n] = sums
    return COUNTS_SUMMING[n]

GENERATE_TREES = {0: ['']}
def generate_trees(n):
    if n not in GENERATE_TREES:
        trees = []
        for counts in counts_summing(n - 1):
            for tree in itertools.product(*(generate_trees(m) for m in counts)):
                trees.append('[{}]'.format(''.join(tree)))
        GENERATE_TREES[n] = trees
    return GENERATE_TREES[n]

def braces(n):
    for n_pairs in range(0, n/2+1):
        for counts in counts_summing(n_pairs):
            for forest in itertools.product(*(generate_trees(m) for m in counts)):
                yield ''.join(forest)

start = time.time()
print(sum(1 for _ in braces(20)))
print(time.time() - start)

bftrees.py

import itertools

def counts_summing(n):
    if n == 0:
        yield []
    else:
        for first in range(1, n+1):
            for rest in counts_summing(n - first):
                yield [first] + rest

def generate_trees(n):
    for counts in counts_summing(n - 1):
        for tree in itertools.product(*(generate_trees(m) for m in counts)):
            yield '[{}]'.format(''.join(tree))

def braces(n):
    for n_pairs in range(0, n/2+1):
        for counts in counts_summing(n_pairs):
            for forest in itertools.product(*(generate_trees(m) for m in counts)):
                yield ''.join(forest)

for tree in braces(9):
    print(tree)

enumbf.py

from itertools import product
try:
    from itertools import izip_longest as zip_longest
except ImportError:
    from itertools import zip_longest


def counts_summing(n):
    if n == 0:
        yield []
    else:
        for first in range(1, n+1):
            for rest in counts_summing(n - first):
                yield [first] + rest


def generate_trees(n):
    for counts in counts_summing(n - 1):
        for tree in product(*(generate_trees(m) for m in counts)):
            yield '[{}]'.format(''.join(tree))


def braces(n):
    for n_pairs in range(0, n//2+1):
        for counts in counts_summing(n_pairs):
            for forest in product(*map(generate_trees, counts)):
                yield ''.join(forest)


def fixed_size_sum(n, width):
    if n == 0:
        yield [0] * width
    elif width <= 0:
        yield []
    elif width == 1:
        yield [n]
    else:
        for i in range(n+1):
            for rest in fixed_size_sum(n - i, width - 1):
                yield [i] + rest


LOOPLESS = {0: ['']}
def loopless(n):
    if n not in LOOPLESS:
        LOOPLESS[n] = [''.join(prog) for prog in product('+-<>', repeat=n)]
    return LOOPLESS[n]


def enumbf(n):
    for brace_pattern in braces(n):
        remaining = n - len(brace_pattern)
        if remaining == 0:
            yield brace_pattern
        else:
            for spaces in fixed_size_sum(remaining, len(brace_pattern) + 1):
                for inserts in product(*map(loopless, spaces)):
                    items = zip_longest(inserts, brace_pattern, fillvalue='')
                    yield ''.join(a + b for a, b in items)


for bf in enumbf(10):
    print(bf)