This notebook was prepared by Rishi Rajasekaran. Source and license info is on GitHub.
* None -> Exception * Negative -> Exception * 0 -> [] * 1 -> ['()'] * 2 -> ['(())', '()()'] * 3 -> ['((()))', '(()())', '(())()', '()(())', '()()()']
Let l
and r
denote the number of left and right parentheses remaining at any given point.
The algorithm makes use of the following conditions applied recursively:
l > 0
.r > l
. Violation of the aforementioned condition produces an unbalanced string of parentheses.l = 0 and r = 0
, then the resultant string produced is balanced.The algorithm can be rephrased as:
l = 0 and r = 0
l > 0
r > l
Complexity:
O(4^n/n^(3/2))
, see Catalan numbers - 1, 1, 2, 5, 14, 42, 132...O(n)
, due to the implicit call stack storing a maximum of 2n function calls)class Parentheses(object):
def find_pair(self, num_pairs):
if num_pairs is None:
raise TypeError('num_pairs cannot be None')
if num_pairs < 0:
raise ValueError('num_pairs cannot be < 0')
if not num_pairs:
return []
results = []
curr_results = []
self._find_pair(num_pairs, num_pairs, curr_results, results)
return results
def _find_pair(self, nleft, nright, curr_results, results):
if nleft == 0 and nright == 0:
results.append(''.join(curr_results))
else:
if nleft >= 0:
self._find_pair(nleft-1, nright, curr_results+['('], results)
if nright > nleft:
self._find_pair(nleft, nright-1, curr_results+[')'], results)
%%writefile test_n_pairs_parentheses.py
import unittest
class TestPairParentheses(unittest.TestCase):
def test_pair_parentheses(self):
parentheses = Parentheses()
self.assertRaises(TypeError, parentheses.find_pair, None)
self.assertRaises(ValueError, parentheses.find_pair, -1)
self.assertEqual(parentheses.find_pair(0), [])
self.assertEqual(parentheses.find_pair(1), ['()'])
self.assertEqual(parentheses.find_pair(2), ['(())',
'()()'])
self.assertEqual(parentheses.find_pair(3), ['((()))',
'(()())',
'(())()',
'()(())',
'()()()'])
print('Success: test_pair_parentheses')
def main():
test = TestPairParentheses()
test.test_pair_parentheses()
if __name__ == '__main__':
main()
Overwriting test_n_pairs_parentheses.py
%run -i test_n_pairs_parentheses.py
Success: test_pair_parentheses