Generate parentheses: brackets and expressions

To generate parentheses is to list every balanced string of n opening and n closing brackets. Backtracking builds such strings one character at a time and never writes a prefix that cannot be finished. The same idea generates other valid structures, such as every way to put operators between digits so that the expression reaches a target. Here are both problems, a brute force with its cost measured, and the signal that points to the search.

Two structures to generate

For n = 1 the only layout is (); n = 2 gives (()) and ()(); n = 3 gives five, from ((())) to ()()().

31415 reaches 17 in two ways, 3*1*4+1*5 and 3*1*4*1+5; 2048 reaches 8 as 2*0*4+8 and 20-4-8. 2005 reaches 7 in six ways, and 2+005 is not one of them.

The brute force, and why it fails at these sizes

The brute force builds every string and keeps the ones that pass a check: all 4ⁿ strings of 2n brackets, and all 4 to the power (digits − 1) ways to fill the gaps between digits, each evaluated by Python’s eval.

# The brute force for both problems: build every string, then keep the ones that pass the check.
import itertools
import re
import time


def balanced(s):
    depth = 0
    for ch in s:
        depth += 1 if ch == "(" else -1
        if depth < 0:
            return False
    return depth == 0


def layouts_brute(n):
    """Every string of 2n brackets, kept when it is balanced."""
    return ["".join(p) for p in itertools.product("()", repeat=2 * n) if balanced("".join(p))]


LEADING_ZERO = re.compile(r"(?<!\d)0\d")


def expressions_brute(digits, target):
    """Every way to put +, -, * or nothing between the digits, each evaluated from scratch."""
    found = []
    for ops in itertools.product(["", "+", "-", "*"], repeat=len(digits) - 1):
        expr = digits[0] + "".join(op + d for op, d in zip(ops, digits[1:]))
        if LEADING_ZERO.search(expr):
            continue  # 05 is not a number here, and eval would raise SyntaxError on it
        if eval(expr) == target:
            found.append(expr)
    return found


print(layouts_brute(3))
print(" n  layouts  strings tried   time")
for n in range(1, 10):
    start = time.perf_counter()
    count = len(layouts_brute(n))
    seconds = time.perf_counter() - start
    print(f"{n:2}  {count:7,}  {4 ** n:13,}  {seconds:5.2f} s")
print(f"n = 12: {4 ** 12:,} strings, about {seconds * 4 ** 3 * 12 / 9:.0f} s at the speed of the last row")

print(expressions_brute("31415", 17), expressions_brute("2048", 8))
start = time.perf_counter()
count = len(expressions_brute("31415926", 100))
seconds = time.perf_counter() - start
print(f"8 digits: {4 ** 7:,} expressions evaluated, {count} equal 100, {seconds:.2f} s")
print(f"10 digits: {4 ** 9:,} expressions, about {seconds * 16 * 10 / 8:.0f} s at that speed")

['((()))', '(()())', '(())()', '()(())', '()()()']
 n  layouts  strings tried   time
 1        1              4   0.00 s
 2        2             16   0.00 s
 3        5             64   0.00 s
 4       14            256   0.00 s
 5       42          1,024   0.00 s
 6      132          4,096   0.00 s
 7      429         16,384   0.01 s
 8    1,430         65,536   0.03 s
 9    4,862        262,144   0.26 s
n = 12: 16,777,216 strings, about 22 s at the speed of the last row
['3*1*4+1*5', '3*1*4*1+5'] ['20-4-8', '2*0*4+8']
8 digits: 16,384 expressions evaluated, 21 equal 100, 0.90 s
10 digits: 262,144 expressions, about 18 s at that speed

The answers are right, and the waste is easy to see. For n = 9 only 4,862 of 262,144 strings are balanced, under 2 %, and n = 12 means 16,777,216 strings for 208,012 layouts. The expressions are worse: each is built and parsed from scratch, so 10 digits mean 262,144 calls to eval, which the measured rate puts at seconds, not milliseconds.

What to notice

• A prefix can already be hopeless. A prefix with more ) than (, or with more than n (, can never become a layout, so a search that grows the string one character at a time can refuse it on the spot.
• Expressions share their beginnings. Every expression starting 3*1*4 repeats the same work up to that point, so carry the value forward instead of evaluating each string again.
• Precedence is the one difficulty. In 1+2*3, the * changes a term that has already been added.

Four techniques follow:

• Two counters, for opening and closing brackets, decide which character may come next.
• The running value and the last term let * replace the last term by its product.
• The leading-zero rule stops an operand from growing once it starts with 0.
• Counting completions finds the k-th layout directly, without listing the ones before it.

Balanced layouts with two counters Pro: opens with a Pro, Premium or Ultimate pass