Nested parentheses in a python one-liner
A colleague at my former employer Cruise Automation asked “How do you print all valid strings of n pairs of nested parentheses with a one-liner?”
“()(())” is valid, because every opening parenthesis is matched by a closing one. “())” is invalid, because the last closing parenthesis is unmatched. Likewise “(())” is valid, “)(” isn’t, and neither is “(()”.
I’m pretty sure he had a work-related reason for wanting it, which I can’t recall. It surely wasn’t about actually printing nested parentheses, but it was some problem which was functionally identical. The problem of generating (or counting) all strings of balanced parentheses is related to the Catalan numbers, and there are lots of ways for these numbers to pop up; see the “Applications in combinatorics” section of the linked wikipedia article.
Can we write this one-liner in python?
After studying the ideas in the wikipedia article linked above, I produce my first attempt:
def nested_parens(n):
if n == 0:
return ['']
parens = []
for i in range(n):
for a in nested_parens(i):
for b in nested_parens(n - 1 - i):
parens.append('(' + a + ')' + b)
return parens
>>> nested_parens(3)
['()()()', '()(())', '(())()', '(()())', '((()))']
That’s longer than one line, but one step at a time. First I’ll explain what it’s doing, then we’ll “improve” it so that it matches the specifications. I put that in quotes because optimizing for the values of “one-liner” destroys its value according to many other measures. It’ll be pretty monstrous.
What is it doing
It’s an example of a recursive function. The base case when n is zero is tested at the beginning, and for larger values 1, 2, 3, ..., the function is defined in terms of smaller values. Note that I didn’t bother to check that the input parameter is sensible — this is meant to be a throwaway one-liner —, but at least range will complain if it gets a bad value so it probably won’t get stuck in an infinite loop.
The idea is that every string of (for example) three properly nested parentheses looks like one of the following:
( ~zero nested parens~ ) ~two nested parens~
( ~one nested paren~ ) ~one nested paren~
( ~two nested parens~ ) ~zero nested parens~
The outermost for is looping over each line of the above, and the two inner fors are looping over the two groups of nested parens in each line. Each group of nested parens in each line is a number smaller than 3, and so the function calls itself recursively.
Improve it: be more pythonic
Let’s improve it! Our goal is to make it a one-liner. Right now it weighs in at 9 lines, plus one line to call the function. Even if we weren’t trying to make it a one-liner, it’s not idiomatic python as it stands. In python, prefer to use list comprehensions instead of iterating over numeric variables.
Attempt number two:
def nested_parens(n):
if n == 0:
return ['']
return ['(' + a + ')' + b
for i in range(n)
for a in nested_parens(i)
for b in nested_parens(n - 1 - i)]
Much better! I think this version is easier to read as well as being more idiomatic python.
Philosophical issues: what is a one-liner?
“Every program is a one-liner, if that line is long enough.” I’ve heard mathematicians make that joke about one-line proofs of theorems, too. Parallel evolution of humor? Or overlapping communities?
It’s hard to make precise exactly what counts as one line. Is the base case of this function one line or two? It’s written as two lines, with if n == 0: on one line and return [''] on a second… but on the other hand the single line if n == 0: return [''] is perfectly correct, even if the convention is to split it up for readability.
Regardless, it’s clear that the program as it stands is not one line. Let’s shorten it. At this point we’re abandoning the value of clarity for the questionable value of abhorring new-lines.
Attempt number three:
def nested_parens(n):
return [''] if n == 0 else ['(' + a + ')' + b
for i in range(n)
for a in nested_parens(i)
for b in nested_parens(n - 1 - i)]
Lovely! I left line breaks inside the list comprehension for readability, but you could get rid of those breaks and the program is the same. So are we done?
Anonymous function calls
I count three lines. One for def nested_parens(n):, a second for the function definition itself (ignoring the line breaks left in for readability), and a third for calling it. For example:
>>> def square(n):
... return n * n
...
>>> square(5)
25
We had to type three lines. Four if you count the empty line to break out of the function definition. Unacceptable! We can modify this toy example to really truly require only one line:
>>> (lambda n: n * n)(5)
25
We’ve replaced the function definition of square with an anonymous function call, or a lambda, and then called that function with the parameter 5 in the same line.
So let’s do the same for our nested parentheses function!
Anonymous recursion
Not so fast.
(Failed) attempt:
>>> (lambda n: [''] if n == 0 else ['(' + a + ')' + b
for i in range(n)
for a in nested_parens(i)
for b in nested_parens(n - 1 - i)])(5)
Traceback (most recent call last):
File "<stdin>", line 4, in <module>
File "<stdin>", line 3, in <lambda>
NameError: global name 'nested_parens' is not defined
An anonymous function can’t refer to itself so easily. How could it? It has no name. (Note: if you’re following along in a terminal and the above seemed to work fine with no error, it’s because you have a previously defined working version of nested_parens. Delete that working version with del nested_parens or by simply relaunching python.)
So how do we implement recursion in an anonymous function? Let’s develop the answer with an easier example of a recursive function, the factorial function:
>>> def factorial(n):
... if n == 0:
... return 1
... return n * factorial(n - 1)
...
>>> factorial(4)
24
Our goal is to rewrite this recursive function in such a way that the function doesn’t actually refer to itself by name, so that we can write it as a lambda. In order to do that we have to first make it seem a bit more complicated:
>>> def factorial(n, recursive_fn):
... if n == 0:
... return 1
... return n * recursive_fn(n - 1, recursive_fn)
...
>>> factorial(4, factorial)
24
What?! Well, the point is that now the factorial function doesn’t refer to itself by name in its definition. We do that at the cost of introducing an extra parameter: the new definition of factorial says, instead of “call myself recursively”, “call this other function recursive_fn recursively”, and then when we call factorial we pass itself in a parameter.
So how do we use this?
>>> def call_fn_on_itself(m, fn):
... return fn(m, fn)
...
>>> call_fn_on_itself(4, factorial)
24
Now we can write factorial as an anonymous function instead of a named function, and call_fn_on_itself will still work:
>>> call_fn_on_itself(
... 4, lambda n, recursive_fn: 1 if n == 0 else
... n * recursive_fn(n-1, recursive_fn))
24
We can write call_fn_on_itself anonymously, too:
>>> (lambda m, fn: fn(m, fn))(4, factorial)
24
And put the two ideas together:
>>> (lambda m, fn: fn(m, fn))(4, lambda n, recursive_fn : 1 if n == 0 else n * recursive_fn(n-1, recursive_fn))
24
And finally, we use the parentheses-generating function instead of factorial:
>>> (lambda m, fn: fn(m, fn))(3, lambda n, recursive_fn : [''] if n == 0 else ['('+a+')'+b for i in range(n) for a in recursive_fn(i, recursive_fn) for b in recursive_fn(n-1-i, recursive_fn)])
['()()()', '()(())', '(())()', '(()())', '((()))']
And there’s our one-liner.
Food for thought
Even within the slightly crazy world of one-liners, there’s still room to improve this function. Interested readers might like to try improving this so that it looks like (...)(3) instead of (...)(3, ...). Another fun improvement would be to arrange matters so that in the function definition for the parenthesis generator you didn’t have to type recursive_fn(i, recursive_fn) but instead could just type recursive_fn(i), and have some other part of the one-liner expand that appropriately.
Additionally, generator comprehensions are probably more appropriate than list comprehensions here, especially if n is largish.